Description
神犇SJY虐完HEOI之后给傻×LYD出了一题：
SHY是T国的公主，平时的一大爱好是作诗。
由于时间紧迫，SHY作完诗之后还要虐OI，于是SHY找来一篇长度为N的文章，阅读M次，每次只阅读其中连续的一段[l,r]，从这一段中选出一些汉字构成诗。因为SHY喜欢对偶，所以SHY规定最后选出的每个汉字都必须在[l,r]里出现了正偶数次。而且SHY认为选出的汉字的种类数（两个一样的汉字称为同一种）越多越好（为了拿到更多的素材！）。于是SHY请LYD安排选法。
LYD这种傻×当然不会了，于是向你请教……
问题简述：N个数，M组询问，每次问[l,r]中有多少个数出现正偶数次。
Input
输入第一行三个整数n、c以及m。表示文章字数、汉字的种类数、要选择M次。
第二行有n个整数，每个数Ai在[1, c]间，代表一个编码为Ai的汉字。
接下来m行每行两个整数l和r，设上一个询问的答案为ans(第一个询问时ans=0)，令L=(l+ans)mod n+1, R=(r+ans)mod n+1，若L>R，交换L和R，则本次询问为[L,R]。
Output
输出共m行，每行一个整数，第i个数表示SHY第i次能选出的汉字的最多种类数。
Range
对于100%的数据，1<=n,c,m<=10^5
Solution
分块。
我们把数列分成 \(\sqrt N\) 块。
记 \(\mathcal{ans[i][j]}\) 表示从 \(l\) 块到 \(r\) 块的答案，可以在 \(\mathcal{O(N\sqrt N)}\) 得到。
记 \(sum[i][j]\) 表示第 \(1-i\) 块数字 \(j\) 出现了多少次，这个我们可以先求出第 \(i\) 块中数字 \(j\) 出现了多少次，然后求前缀和即可。这个可以在 \(\mathcal{O(C\sqrt N)}\) 内得到。
对于询问区间 \([l,r]\)，我们可以从 \(ans\) 数组中快速求出中间连续的完整的块的答案。
对于剩余部分，我们可以一个一个调整答案，反正剩余部分的长度是 \(\sqrt N\) 级别的。
ps:判断一个数是不是偶数时不能简单的
if(i^1) ...如果这样判断，只要 \(i\) 不为 \(0\)，那么这个值一定为真。
#include<cmath>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<iostream>
#define N 100005int tot;
int n,c,m;
int val[N];
int cnt[N];
int sum[405][N];
int l[405],r[405];
int ans[405][405];
int block,belong[N];void read(int &x){x=0; char ch=getchar();while(!isdigit(ch)) ch=getchar();while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
}int query(int x,int y){if(belong[x]==belong[y] or belong[x]+1==belong[y]){int now=0;for(int i=x;i<=y;i++){cnt[val[i]]++;if(cnt[val[i]]%2==0) now++;else if(cnt[val[i]]>2) now--;}memset(cnt,0,sizeof cnt);return now;}int now=ans[belong[x]+1][belong[y]-1];for(int i=x;i<=r[belong[x]];i++)cnt[val[i]]++;for(int i=y;i>=l[belong[y]];i--)cnt[val[i]]++;for(int i=x;i<=r[belong[x]];i++){if(cnt[val[i]]){int tmp=sum[belong[y]-1][val[i]]-sum[belong[x]][val[i]];//printf("tmp=%d\n",tmp);if(!tmp and (cnt[val[i]]%2==0)) now++;else if(tmp and (tmp&1) and (cnt[val[i]]&1)) now++;else if(tmp and (tmp%2==0) and (cnt[val[i]]&1)) now--;cnt[val[i]]=0;}}for(int i=y;i>=l[belong[y]];i--){if(cnt[val[i]]){int tmp=sum[belong[y]-1][val[i]]-sum[belong[x]][val[i]];//printf("tmp=%d\n",tmp);if(!tmp and (cnt[val[i]]%2==0)) now++;else if(tmp and (tmp&1) and (cnt[val[i]]&1)) now++;else if(tmp and (tmp%2==0) and (cnt[val[i]]&1)) now--;cnt[val[i]]=0;}}return now;
}void file(){freopen("in.txt","r",stdin);freopen("out1.txt","w",stdout);
}signed main(){//file();read(n),read(c),read(m);block=sqrt((double)n);tot=n/block;if(n%block) tot++;for(int i=1;i<=n;i++){scanf("%d",&val[i]);belong[i]=(i-1)/block+1;sum[belong[i]][val[i]]++;}for(int i=1;i<=tot;i++){l[i]=(i-1)*block+1;r[i]=i*block;for(int j=1;j<=c;j++) sum[i][j]+=sum[i-1][j];}/*for(int i=1;i<=tot;i++){for(int j=1;j<=c;j++)printf("i=%d,j=%d,sum=%d\n",i,j,sum[i][j]);}*/for(int i=1;i<=tot;i++){int now=0;for(int j=l[i];j<=n;j++){cnt[val[j]]++;if(cnt[val[j]]%2==0) now++;else if(cnt[val[j]]>2) now--;ans[i][belong[j]]=now;}/*for(int j=l[i];j<=n;j++)cnt[val[j]]--;*/memset(cnt,0,sizeof cnt);}int last=0;while(m--){int a,b,x,y;read(a),read(b);x=(a+last)%n+1;y=(b+last)%n+1;if(x>y) x^=y^=x^=y;printf("%d\n",last=query(x,y));}return 0;
}