[Luogu 4135] 作诗
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 100005
int 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;
}