前言：世间还有这么卡常的题……
------------------
题目大意：给定长度为$n$的序列${a_i}$。有$m$次询问，问$[l,r]$内出现正偶数次的数字有多少个。
这题跟蒲公英有些相似，不同的是这题特别卡常……
设$sum[i][j]$表示前$i$块内$j$出现的次数，$ans[i][j]$表示块$i$到$j$的答案。
主要的问题是怎么在$O(n sqrt n)$内进行预处理。我们采用“边扫边求”的方式来进行处理，扫的时候开一个桶，注意不要重复统计。对于$ans[i][j]$，我们有：
设$t$为块$i$到$j-1$内数$k$出现的次数。
1.如果$t$是奇数并且$bucket[k]$也是奇数，那么$ans[i][j]++$。
2.如果$t$是偶数并且$bucket[k]$是奇数，那么$ans[i][j]--$。
剩下的就跟蒲公英的处理差不多了。注意不要使用memset!!!!!!（血与泪的教训QAQ）
代码：
//求l到r中出现偶次的数字的个数 #include<bits/stdc++.h> using namespace std; int sum[405][100005],ans[405][405];//sum 前i块中j出现的次数 ans 从i块到j块的答案 int n,m,c,a[100005],l,r,block,tot,t,vis[100005],bucket[100005],last; inline int read() { int x=0,f=1;char ch=getchar(); while(!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();} while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();} return x*f; } inline int getpos(int x){return (x-1)/block+1;} inline void build() { for (int i=1;i<=tot;i++) { for (int j=1;j<=c;j++) sum[i][j]=sum[i-1][j]; for (int j=(i-1)*block+1;j<=i*block;j++) sum[i][a[j]]++; } for (int i=1;i<=tot;i++) for (int j=i;j<=tot;j++) { ans[i][j]=ans[i][j-1]; for (int k=(j-1)*block+1;k<=j*block;k++) { if (!vis[a[k]]) vis[a[k]]=1,bucket[a[k]]=1; else bucket[a[k]]++; } for (int k=(j-1)*block+1;k<=j*block;k++) { if (!vis[a[k]]) continue; vis[a[k]]=0; int t=sum[j-1][a[k]]-sum[i-1][a[k]]; if (!t){if (bucket[a[k]]%2==0) ans[i][j]++;} else{ if (t%2==1&&bucket[a[k]]%2==1) ans[i][j]++; else if (t%2==0&&bucket[a[k]]%2==1) ans[i][j]--; } } } } inline void query() { int cnt=0; if (getpos(r)-getpos(l)<=1) { for (int i=l;i<=r;i++) { if (!vis[a[i]]) vis[a[i]]=1,bucket[a[i]]=1; else bucket[a[i]]++; } for (int i=l;i<=r;i++) { if (!vis[a[i]]) continue; vis[a[i]]=0; if (bucket[a[i]]%2==0) cnt++; } printf("%d ",cnt);last=cnt; return; } cnt=ans[getpos(l)+1][getpos(r)-1]; for (int i=l;i<=getpos(l)*block;i++) { if (!vis[a[i]]) vis[a[i]]=1,bucket[a[i]]=1; else bucket[a[i]]++; } for (int i=(getpos(r)-1)*block+1;i<=r;i++) { if (!vis[a[i]]) vis[a[i]]=1,bucket[a[i]]=1; else bucket[a[i]]++; } for (int i=l;i<=getpos(l)*block;i++) { if (!vis[a[i]]) continue; vis[a[i]]=0; int t=sum[getpos(r)-1][a[i]]-sum[getpos(l)][a[i]]; if (!t){if (bucket[a[i]]%2==0) cnt++;} else{ if (t%2==1&&bucket[a[i]]%2==1) cnt++; if (t%2==0&&bucket[a[i]]%2==1) cnt--; } } for (int i=(getpos(r)-1)*block+1;i<=r;i++) { if (!vis[a[i]]) continue; vis[a[i]]=0; int t=sum[getpos(r)-1][a[i]]-sum[getpos(l)][a[i]]; if (!t){if (bucket[a[i]]%2==0) cnt++;} else{ if (t%2==1&&bucket[a[i]]%2==1) cnt++; if (t%2==0&&bucket[a[i]]%2==1) cnt--; } } printf("%d ",cnt);last=cnt; } int main() { n=read(),c=read(),m=read(); block=sqrt(n); tot=n/block; if (n%block) tot++; for (int i=1;i<=n;i++) a[i]=read(); build(); for (int i=1;i<=m;i++) { l=read(),r=read(); l=(l+last)%n+1,r=(r+last)%n+1; if (l>r) swap(l,r); query(); } return 0; }