https://www.luogu.com.cn/problem/P4135
https://darkbzoj.tk/problem/2821
前缀和写的时候一开始原数组、前缀和数组分开来的，结果 bzoj MLE，和在一起才过的。。。
给定一个长度为 (n) 的数列，(m) 个询问，每次问 ([l,r]) 中有多少种数的出现次数为偶数，强制在线，(n,m,max{a_i}le 10^5)
区间问题，但线段树啥的又不好维护，考虑分块
单独维护每个块的信息然后一个个合并肯定没戏，所以考虑每次询问只合并边角块和中间一部分整块的信息
这样需要一个 (f_{l,r}) 来表示 ([l,r]) 块的答案，然后枚举边角块里的没一个元素，记录下每一个值出现了多少次，容易知道可以按照下面两条规则统计最终答案
- 如果一个值在整块中出现了奇数次，或者没出现，那么如果在整块出现的次数和在两个边角块出现的次数的奇偶性相同，则这个值一共出现了偶数次，答案加一
- 如果在整块中出现了偶数次，且不为零，那么如果在两个边角块中出现了奇数次，答案减一
那么也就需要一个 (sum_{i,k}) 表示前 (i) 块，(k) 出现了几次
按照上面的想法，也就可以 (O(nsqrt n)) 的预处理出 (f) 了（由 (f_{l,r-1}) 推知 (f_{l,r})）
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define reg register
inline int read(){
int x=0,y=1;
char c=std::getchar();
while(c<'0'||c>'9'){if(c=='-') y=-1;c=std::getchar();}
while(c>='0'&&c<='9'){x=x*10+(c^48);c=std::getchar();}
return x*y;
}
#define N 100005
#define SQRTN 320
int n,m,B,c;
int block[N],a[N];
int L[SQRTN],R[SQRTN],sum[SQRTN][N],f[SQRTN][SQRTN];
int tmp[N];
inline void pre(){
for(reg int i=1;i<=block[n];i++)
for(reg int j=1;j<=c;j++) sum[i][j]+=sum[i-1][j];
for(reg int i=1;i<=block[n];i++){
for(reg int j=L[i];j<=R[i];j++) tmp[a[j]]++;
for(reg int j=L[i];j<=R[i];j++) f[i][i]+=(tmp[a[j]]&&!(tmp[a[j]]&1)),tmp[a[j]]=0;
for(reg int j=i+1;j<=block[n];j++){
for(reg int k=L[j];k<=R[j];k++) tmp[a[k]]++;
f[i][j]=f[i][j-1];
for(reg int kk=L[j],k;kk<=R[j];kk++)if(tmp[a[kk]]){
k=a[kk];
if(sum[j-1][k]-sum[i-1][k]>0&&!((sum[j-1][k]-sum[i-1][k])&1)) f[i][j]-=(tmp[k]&1);
//[i,j-1] 上 k 的个数为偶数，且不等于 0，则 tmp[k] 为奇数答案就减一
else if((tmp[k]&1)==((sum[j-1][k]-sum[i-1][k])&1)) f[i][j]++;
//为奇数，或为 0，则 tmp[k] 与之前 k 的个数奇偶性相同，f[i][j] 就加一
tmp[k]=0;
}
}
}
}
//inline void print(){
// puts("block :");
// for(reg int i=1;i<=n;i++) printf("%d : %d,left : %d,right : %d
",i,block[i],L[block[i]],R[block[i]]);
// puts("
sum :");
// for(reg int i=1;i<=block[n];i++){
// printf("block %d :
",i);
// for(reg int j=1;j<=c;j++) printf("%d ",sum[i][j]);
// puts("
");
// }
// puts("
f :");
// for(reg int i=1;i<=n;i++){
// for(reg int j=i;j<=block[n];j++) printf("f[%d][%d]=%d ",i,j,f[i][j]);
// puts("");
// }
//}
int main(){
n=read();c=read();m=read();B=std::sqrt(n);
std::memset(L,0x3f,sizeof L);
for(reg int i=1;i<=n;i++){
a[i]=read();
block[i]=block[i-1]+(!((i-1)%B));
sum[block[i]][a[i]]++;
R[block[i]]=std::max(R[block[i]],i);L[block[i]]=std::min(L[block[i]],i);
}
pre();
// print();
reg int l,r,bl,br;int ans=0;
while(m--){
l=(ans+read())%n+1;r=(ans+read())%n+1;
if(l>r) l^=r,r^=l,l^=r;
bl=block[l];br=block[r];
if(bl==br){
for(reg int i=l;i<=r;i++) tmp[a[i]]++;
ans=0;
for(reg int i=l;i<=r;i++) ans+=(tmp[a[i]]&&!(tmp[a[i]]&1)),tmp[a[i]]=0;
printf("%d
",ans);
continue;
}
for(reg int i=l;i<=R[bl];i++) tmp[a[i]]++;
for(reg int i=L[br];i<=r;i++) tmp[a[i]]++;
ans=f[bl+1][br-1];
for(reg int k,i=l;i<=R[bl];i++)if(tmp[a[i]]){
k=a[i];
if(sum[br-1][k]-sum[bl][k]>0&&!((sum[br-1][k]-sum[bl][k])&1)) ans-=(tmp[k]&1);
else if((tmp[k]&1)==((sum[br-1][k]-sum[bl][k])&1)) ans++;
tmp[k]=0;
}
for(reg int k,i=L[br];i<=r;i++)if(tmp[a[i]]){
k=a[i];
if(sum[br-1][k]-sum[bl][k]>0&&!((sum[br-1][k]-sum[bl][k])&1)) ans-=(tmp[k]&1);
else if((tmp[k]&1)==((sum[br-1][k]-sum[bl][k])&1)) ans++;
tmp[k]=0;
}
printf("%d
",ans);
}
}