NOIP模拟赛 T3区间

题目大意

有$n$个数字，第$i$个数字为$a_i$。有$m$次询问，每次给出$k_i$个区间，每个区间表示第$l_{i,j}$到第$r_{i,j}$个数字，求这些区间中一共出现了多少种不同的数字。部分数据强制在线。

时限1s，空间8MB。

输入格式

第一行包括三个整数$n,m,p$，$p$为$0$或$1$表示是否强制在线。

第二行$n$个正整数，第$i$个表示$a_i$。

接下来依次给出每个询问，每个询问第一行一个正整数，表示$k_i$。接下来$k_i$行，每行两个正整数，分别表示$l_{i,j}$和$r_{i,j}$。

若$p=1$且这不是第一个询问，则输入的$l_{i,j}$和$r_{i,j}$是经过加密的，你需要将这两个数字分别异或上上一个询问的答案，对$n$取模后再加$1$，两者的较小值为真实的$l_{i,j}$，较大值为真实的$r_{i,j}$。

输出格式

对每个询问输出一行一个整数表示答案。

输入样例

3 2 0
1 2 1
1
1 2
2
1 1
3 3

输出样例

2
1

数据范围

$1\le n,m,\sum k_i,a_i\le 10^5,1\le l_{i,j}\le r_{i,j}\le n$

题解

首先，我们考虑$p=0$的情况。

我们可以用$bitset$来维护每个点是否出现。先把各个区间离线下来，用莫队求出每个区间的$bitset$。把每个询问并起来。这样做的时间复杂度为$O(n\sqrt{n}+\frac{nm}{64})$。

空间开不下，我们考虑优化。

既然要用$bitset$，那么时间复杂度肯定是要带$\frac{nm}{64}$的了。我们不妨将每$\frac{n}{64}$个元素分一块，对于每次询问，非整块的暴力处理，再预处理整块到整块的$bitset$即可。

空间开不下，就对这$64$个块建$ST$表。建$ST$表不用倍增，对每种长度从左到右推一遍即可。

在优化一下常数。只出现过一次的权值，把它们单独求一个前缀和，每次特殊处理即可。这样的话，每个权值至少出现两次，离散化之后权值个数能减少至少一半。

离散化的时间复杂度为$O(n\log n)$，建$ST$表的时间复杂度为$O(n\log 64)$，查询的时间复杂度为$O(\frac{nm}{64}+64n)$，总时间复杂度为$O(\frac{nm}{64})$。因为权值个数减半，所以时间复杂度能降低到$O(\frac{nm}{128})$。

空间复杂度为$O(n\log 64)$。

这道题有一定的思维难度，可以结合代码帮助理解。

code

#include<bits/stdc++.h>
#define N 100032
#define K 1563
#define Z 782
using namespace std;
int n,m,p,c1=0,lst,ans,a[N+5],s[1<<16],t[105],c[N+5],sum[N+5];
struct pt{unsigned long long z[Z];void set(int x){z[x>>6]|=1ull<<(x&63);}void rev(int x){z[x>>6]^=1ull<<(x&63);}int count(){int re=0;for(int i=0;i<Z;i++){re+=s[z[i]>>48]+s[(z[i]>>32)&65535]+s[(z[i]>>16)&65535]+s[z[i]&65535];}return re;}
}v,b[6][70];//按颜色分成64块
struct node{int l,r;
}w[N+5];
bool cmp(node ax,node bx){if(ax.l!=bx.l) return ax.l<bx.l;return ax.r<bx.r;
}
void kuai(int l,int r){if(l>r) return;int x=t[r-l+1];for(int i=0;i<Z;i++){v.z[i]|=b[x][l].z[i]|b[x][r-(1<<x)+1].z[i];}
}//所有大块处理
void dd(int l,int r){if((l-1)/K==(r-1)/K){for(int i=l;i<=r;i++) v.set(a[i]);}else{for(int i=l;i<=(l-1)/K*K+K;i++) v.set(a[i]);kuai((l-1)/K+1,(r-1)/K-1);for(int i=(r-1)/K*K+1;i<=r;i++) v.set(a[i]);}
}//分块
int main()
{scanf("%d%d%d",&n,&m,&p);for(int i=2;i<=64;i++) t[i]=t[i>>1]+1;for(int i=1;i<1<<16;i++) s[i]=s[i>>1]+(i&1);for(int i=1;i<=n;i++){scanf("%d",&a[i]);++c[a[i]];}for(int i=1;i<=n;i++){sum[i]=sum[i-1];if(c[a[i]]==1){a[i]=0;++sum[i];}}//若只出现过一次，放到前缀和数组中for(int i=1;i<=n;i++){if(a[i]) c[++c1]=a[i];}sort(c+1,c+c1+1);c1=unique(c+1,c+c1+1)-c-1;for(int i=1;i<=n;i++){if(a[i]){a[i]=lower_bound(c+1,c+c1+1,a[i])-c;}}//离散化for(int i=0,x=K;i<6;i++,x<<=1){memset(v.z,0,sizeof(v.z));memset(c,0,sizeof(c));for(int j=1;j<=x;j++){if(!c[a[j]]) v.rev(a[j]);++c[a[j]];}b[i][0]=v;for(int j=K;j+x<=N;j+=K){for(int k=0;k<K;k++){if(!c[a[j+x-k]]) v.rev(a[j+x-k]);++c[a[j+x-k]];--c[a[j-k]];if(!c[a[j-k]]) v.rev(a[j-k]);}b[i][j/K]=v;}//按位置分成64块}//ST表for(int o=1,k,l,r;o<=m;o++){ans=0;memset(v.z,0,sizeof(v.z));scanf("%d",&k);for(int i=1;i<=k;i++){scanf("%d%d",&w[i].l,&w[i].r);if(p&&o>1){w[i].l=(w[i].l^lst)%n+1;w[i].r=(w[i].r^lst)%n+1;if(w[i].l>w[i].r) swap(w[i].l,w[i].r);}}sort(w+1,w+k+1,cmp);l=w[1].l;r=w[1].r;for(int i=2;i<=k;i++){if(w[i].l>r+1){ans+=sum[r]-sum[l-1];dd(l,r);l=w[i].l;}r=max(r,w[i].r);}ans+=sum[r]-sum[l-1];dd(l,r);//合并区间ans+=v.count()-(v.z[0]&1);//z[0]的第一个位置是为0的a值，不统计lst=ans;printf("%d\n",ans);//求答案}return 0;
}