每次询问一段区间中出现了偶数次的数有多少个。
可离线：
莫队。
直接暴力枚举每一个区间然后在每次加的时候判断一下即可。
强制在线：
分块。
和蒲公英很类似的处理办法，要预处理的有：
所以每次询问就相当于先找一下预处理的答案。然后枚举两个小块，然后枚举在这两个块中出现的每一个元素就可以统计了。
时间复杂度 (O(nsqrt{n})) 。
代码：
#include<bits/stdc++.h>
const int N=1e5+5,M=254;
#define L(x) (n*((x)-1)/m+1)
#define R(x) (n*(x)/m)
using namespace std;
template <typename T>
inline void read(T &x){
x=0;char ch=getchar();bool f=false;
while(!isdigit(ch)){if(ch=='-'){f=true;}ch=getchar();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
x=f?-x:x;
return ;
}
template <typename T>
inline void write(T x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10^48);
return ;
}
int n,a[N],l,bl[N],m,F[M][M],s[N][M],cnt[N];
int Query(int l,int r){
int now=F[bl[l]+1][bl[r]-1];
if (bl[l]==bl[r]){
for(int i=l;i<=r;i++){
if((++cnt[a[i]])<2) continue;
now-=(cnt[a[i]]&1)*2-1;
}
for(int i=l;i<=r;i++) --cnt[a[i]];
return now;
}
for(int i=l;i<=r;i=(i==R(bl[l])?L(bl[r]):(i+1))){
if((++cnt[a[i]])+s[a[i]][bl[r]-1]-s[a[i]][bl[l]]<2) continue;
now-=((cnt[a[i]]+s[a[i]][bl[r]-1]-s[a[i]][bl[l]])&1)*2-1;
}
for (int i=l;i<=r;i=(i==R(bl[l])?L(bl[r]):(i+1))) --cnt[a[i]];
return now;
}
int main(){
read(n),read(l);int Q,ans=0;read(Q);
for (int i=1;i<=n;i++) read(a[i]);
m=min((int)sqrt(n),230);
memset(cnt,0,sizeof(cnt));
for (int i=1;i<=m;i++){
for (int j=L(i);j<=R(i);j++){
bl[j]=i;++cnt[a[j]];
}
for (int j=1;j<=l;j++) s[j][i]=cnt[j];
}
memset(F,0,sizeof(F));
for (int i=1;i<=m;i++){
memset(cnt,0,sizeof(cnt));
int now=0;
for(int j=i;j<=m;j++){
for(int k=L(j);k<=R(j);++k){
if((++cnt[a[k]])<2) continue;
now-=(cnt[a[k]]&1)*2-1;
}
F[i][j]=now;
}
}
memset(cnt,0,sizeof(cnt));
while(Q--){
int X,Y;read(X),read(Y);
int x=(X+ans)%n+1,y=(Y+ans)%n+1;
ans=Query(min(x,y),max(x,y));
write(ans),putchar('
');
}
return 0;
}