目前本人在线。如果调出了错误，会及时在此贴中更新
我和题解的做法不同，是边建树边进行查询，其他没什么区别
如果你有什么优化的思路，也可以回复我
#include<bits/stdc++.h>
using namespace std;
#define lc p<<1
#define rc p<<1|1
const int N=515,M=500010;
struct tree
{
int l,r;
bitset<N> b;
};
struct node
{
tree tr[4*N];
};
struct cxzy//查询专用->cxzy
{
int l1,r1,l2,r2,id,ans;
};
int a[N][N],lg[100010],q,n,len,qu[M],tjcnt;
vector<cxzy> vis[M];
node dp[N];
bitset<N> ansb;
//->初始化
void init()
{
len=1;
while(len<n)
{
len<<=1;
tjcnt++;
}
lg[1]=0;
lg[2]=1;
for(int i=3;i<=100005;i++)
{
lg[i]=lg[i/2]+1;
}
}
//->建树（线段树）（内层）
void ubuild(int idx,int p,int l,int r)
{
dp[idx].tr[p].l=l;
dp[idx].tr[p].r=r;
if(l==r)
{
dp[idx].tr[p].b.reset();
dp[idx].tr[p].b[a[idx][l]]=1;
return;
}
int mid=l+r>>1;
ubuild(idx,lc,l,mid);
ubuild(idx,rc,mid+1,r);
dp[idx].tr[p].b=dp[idx].tr[lc].b|dp[idx].tr[rc].b;
return;
}
//->线段树合并
void huo(int idx1,int idx2,int p,int l,int r)
{
dp[idx1].tr[p].b=dp[idx1].tr[p].b|dp[idx2].tr[p].b;
if(l==r)
{
return;
}
int mid=l+r>>1;
huo(idx1,idx2,lc,l,mid);
huo(idx1,idx2,rc,mid+1,r);
return;
}
//->线段树查询
void uquery(int idx,int p,int l,int r)
{
int ll=dp[idx].tr[p].l,rr=dp[idx].tr[p].r;
if(l<=ll&&rr<=r)
{
ansb=ansb|dp[idx].tr[p].b;
return;
}
int mid=ll+rr>>1;
if(mid>=l)uquery(idx,lc,l,r);
if(mid<r)uquery(idx,rc,l,r);
return;
}
//->建树（猫树）（一边建一边回答）（外层）
void build(int p,int l,int r,int d)
{
int mid=l+r>>1;
if(vis[p].size()!=0)
{
for(int i=mid+1;i<=r;i++)
{
ubuild(i,1,1,n);
if(i!=mid+1)
{
huo(i,i-1,1,1,n);
}
}
for(int i=mid;i>=l;i--)
{
ubuild(i,1,1,n);
if(i!=mid)
{
huo(i,i+1,1,1,n);
}
}
cxzy j;
for(int i=0;i<vis[p].size();i++)
{
j=vis[p][i];
ansb.reset();
uquery(vis[p][i].r1,1,vis[p][i].l2,vis[p][i].r2);
uquery(vis[p][i].l1,1,vis[p][i].l2,vis[p][i].r2);
ansb[0]=0;
vis[p][i].ans=ansb.count();
}
}
if(l==r)
{
return;
}
build(lc,l,mid,d+1);
build(rc,mid+1,r,d+1);
}
//->查询预处理
int ggqz(int x, int y)//ggqz->公共前缀
{
if(x==y)return x;
int mask=0;
int bitx,bity,ccnt;
for(int i=20;i>=0;i--)
{
bitx=(x>>i)&1;
bity=(y>>i)&1;
if(bitx!=bity)
{
break;
}
mask|=(bitx<<i);
ccnt=i;
}
while(ccnt>=1)
{
mask>>=1;
ccnt--;
}
return mask;
}
int lsbl;
inline void quu(int l1,int r1,int l2,int r2,int idx)
{
lsbl=ggqz((1<<tjcnt)+l1-1,(1<<tjcnt)+r1-1);
vis[lsbl].push_back({l1,r1,l2,r2,idx,0});
}
//<-查询预处理
int main()
{
freopen("genshin.in","r",stdin);
freopen("genshin.out","w",stdout);
cin>>n;
init();
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
cin>>a[i][j];
}
}
int l1,r1,l2,r2;
cin>>q;
for(int i=1;i<=q;i++)
{
cin>>l1>>r1>>l2>>r2;
quu(l1,r1,l2,r2,i);
}
build(1,1,len,1);
for(int i=1;i<=2*len;i++)
{
for(int j=0;j<vis[i].size();j++)
{
qu[vis[i][j].id]=vis[i][j].ans;
}
}
for(int i=1;i<=q;i++)
{
cout<<qu[i]<<endl;
}
}
/*
3
1 2 3
2 3 1
3 1 2
1
1 1 1 1
*/
下面这代码出现了莫名其妙的问题(确认问题在quu里，可能和vector有关系)（只要q超过10就RE）但空间已经优化，虽然还是MLE，但我后期再松一松应该能过
#include<bits/stdc++.h>
using namespace std;
#define lc p<<1
#define rc p<<1|1
const int N=2060,M=500010;
struct tree
{
int l,r;
bitset<N> b;
};
tree tr[4*N];
struct quer
{
int l,r,id;
bitset<N> ans;
};
int a[N][N],q,n,len,tjcnt;
vector<quer> mp1[2*N][N],mp2[2*N][N];
bitset<N> ansb;
bitset<N> qu[M];
//->初始化
void init()
{
len=1;
while(len<n)
{
len<<=1;
tjcnt++;
}
}
//->建树（线段树或合并）（内层） 修改完成
void ubuild(int idx,int p,int l,int r)
{
tr[p].l=l;
tr[p].r=r;
if(l==r)
{
tr[p].b[a[idx][l]]=1;
return;
}
int mid=l+r>>1;
ubuild(idx,lc,l,mid);
ubuild(idx,rc,mid+1,r);
tr[p].b=tr[lc].b|tr[rc].b;
return;
}
//->线段树清零 修改完成
void clear(int p,int l,int r)
{
tr[p].b.reset();
tr[p].l=0;
tr[p].r=0;
if(l==r)
{
return;
}
int mid=l+r>>1;
clear(lc,l,mid);
clear(rc,mid+1,r);
return;
}
//->线段树查询 修改完成
void uquery(int p,int l,int r)
{
int ll=tr[p].l,rr=tr[p].r;
if(l<=ll&&rr<=r)
{
ansb=ansb|tr[p].b;
return;
}
int mid=ll+rr>>1;
if(mid>=l)uquery(lc,l,r);
if(mid<r)uquery(rc,l,r);
return;
}
//->建树（猫树）（一边建一边回答）（外层） 修改完成
void build(int p,int l,int r)
{
int mid=l+r>>1;
ansb.reset();
for(int i=mid+1;i<=r;i++)
{
ubuild(i,1,1,n);
ansb[0]=0;
for(int j=0;j<mp2[p][i].size();j++)
{
uquery(p,mp2[p][i][j].l,mp2[p][i][j].r);
mp2[p][i][j].ans=ansb;
}
}
clear(1,1,n);
ansb.reset();
for(int i=mid;i>=l;i--)
{
ubuild(i,1,1,n);
ansb[0]=0;
for(int j=0;j<mp1[p][i].size();j++)
{
uquery(p,mp1[p][i][j].l,mp1[p][i][j].r);
mp1[p][i][j].ans=ansb;
}
}
if(l==r)
{
return;
}
build(lc,l,mid);
build(rc,mid+1,r);
}
//->查询预处理
int ggqz(int x, int y)//ggqz->公共前缀 修改完成
{
if(x==y)return x;
int mask=0;
int bitx,bity,ccnt;
for(int i=20;i>=0;i--)
{
bitx=(x>>i)&1;
bity=(y>>i)&1;
if(bitx!=bity)
{
break;
}
mask|=(bitx<<i);
ccnt=i;
}
while(ccnt>=1)
{
mask>>=1;
ccnt--;
}
return mask;
}
int lsbl;
inline void quu(int l1,int r1,int l2,int r2,int idx)// 修改完成
{
lsbl=ggqz((1<<tjcnt)+l1-1,(1<<tjcnt)+r1-1);
mp1[lsbl][l1].push_back({l2,r2,idx,bitset<N>(0)});
mp2[lsbl][r1].push_back({l2,r2,idx,bitset<N>(0)});
}
//<-查询预处理
int main()
{
freopen("genshin.in","r",stdin);
freopen("genshin.out","w",stdout);
scanf("%d",&n);
init();
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
scanf("%d",&a[i][j]);
}
}
int l1,r1,l2,r2;
scanf("%d",&q);
for(int i=1;i<=q;i++)
{
scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
quu(l1,r1,l2,r2,i);
}
build(1,1,len);
for(int i=1;i<=2*len;i++)
{
for(int j=1;j<=n;j++)
{
for(int k=0;k<mp1[i][j].size();k++)
{
qu[mp1[i][j][k].id]=qu[mp1[i][j][k].id]|mp1[i][j][k].ans;
}
for(int k=0;k<mp2[i][j].size();k++)
{
qu[mp2[i][j][k].id]=qu[mp2[i][j][k].id]|mp2[i][j][k].ans;
}
}
}
for(int i=1;i<=q;i++)
{
printf("%d\n",qu[i].count());
}
}
/*
3
1 2 3
2 3 1
3 1 2
1
1 1 1 1
*/
