//应该是算法有问题，希望能帮我优化一下常数或者改进一下算法
寒假趣味做题 - 信友队
给定一个 n 行 n 列且值域为 [1,n] 的正整数方阵a 和 q 个询问。
每次询问给一个a的子矩阵的左上角坐标，右下角坐标，求子矩阵内的元素种类数
n=2000,q=500000
#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define rc p<<1|1
#define lc p<<1
const int N=2010,c=0,K=61;
int n,a[N][N];
struct node
{
ull a[N/K+10];
int l,r;
};
struct tree
{
node tr[N/8+10];
int l,r;
};
tree s[2*N+10];
ull x[N/K+3];
void init(int idx,int p,int l,int r)
{
s[idx].tr[p].l=l;
s[idx].tr[p].r=r;
if(r-l<=c)
{
int cnt;
for(int i=l;i<=r;i++)
{
cnt=a[s[idx].l][i];
s[idx].tr[p].a[cnt/K]|=(1ll<<(cnt%K));
}
return;
}
int mid=l+r>>1;
init(idx,lc,l,mid);
init(idx,rc,mid+1,r);
for(int i=0;i<=N/K+1;i++)
{
s[idx].tr[p].a[i]=s[idx].tr[lc].a[i]|s[idx].tr[rc].a[i];
}
return;
}
void hb(int idx,int p,int l,int r)
{
s[idx].tr[p].l=l;
s[idx].tr[p].r=r;
for(int i=0;i<=N/K+1;i++)
{
s[idx].tr[p].a[i]=s[idx<<1].tr[p].a[i]|s[idx<<1|1].tr[p].a[i];
}
if(s[idx].tr[p].r-s[idx].tr[p].l<=c)
{
return;
}
int mid=l+r>>1;
hb(idx,lc,l,mid);
hb(idx,rc,mid+1,r);
return;
}
void build(int p,int l,int r)
{
s[p].l=l;
s[p].r=r;
if(l==r)
{
init(p,1,1,n);
return;
}
int mid=l+r>>1;
build(lc,l,mid);
build(rc,mid+1,r);
hb(p,1,1,n);
return;
}
void uquery(int idx,int p,int l,int r)
{
if(s[idx].tr[p].r<=r&&s[idx].tr[p].l>=l)
{
for(int i=0;i<=n/K+3;i++)
{
x[i]=x[i]|s[idx].tr[p].a[i];
}
return;
}
if(s[idx].tr[p].r-s[idx].tr[p].l<=c)
{
int cnt;
for(int i=s[idx].l;i<=s[idx].r;i++)
{
for(int j=max(s[idx].tr[p].l,l);j<=min(r,s[idx].tr[p].r);j++)
{
cnt=a[i][j];
x[cnt/K]|=(1ll<<(cnt%K));
}
}
return;
}
int mid=s[idx].tr[p].l+s[idx].tr[p].r>>1;
if(l<=mid)uquery(idx,lc,l,r);
if(r>mid)uquery(idx,rc,l,r);
return;
}
void query(int p,int x1,int y1,int x2,int y2)
{
if(x1<=s[p].l&&s[p].r<=x2)
{
uquery(p,1,y1,y2);
return;
}
int mid=s[p].l+s[p].r>>1;
if(x1<=mid)query(lc,x1,y1,x2,y2);
if(x2>mid)query(rc,x1,y1,x2,y2);
return;
}
int main()
{
freopen("genshin.in","r",stdin);
freopen("genshin.out","w",stdout);
cin>>n;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
scanf("%d",&a[i][j]);
}
}
build(1,1,n);
int q;
cin>>q;
int l1,l2,r1,r2,ans;
for(int i=1;i<=q;i++)
{
ans=0;
for(int j=0;j<=N/K;j++)
x[j]=0;
scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
query(1,l1,l2,r1,r2);
for(int j=0;j<=n+70;j++)
{
ans+=((x[j/K]|(1ll<<(j%K)))==x[j/K]);
}
printf("%d\n",ans);
}
}