?
题目分析：
首先给出一段序列，共?m?次询问，每一次询问求出给定区间内出现正偶数次数的个数。
算法讲解：
首先，如果忽略本题强制在线的话，可以用莫队来做。
但是，题目中已经规定了需要强制在线来做，于是只能另求他法。
看到数据范围，再结合一下题意，这道题可以用分块来做。
首先，定义两个数组cnt[i][j]表示前i块中j出现的次数ans[i][j]表示第i到第j个块中，出现偶数次数的个数。
这两个数组需要先预处理出来，先来看cnt数组。
相当于一个前缀和的思想，先输入把每一个数+1，然后依次枚举块，把前一块中这个数的出现次数加起来。
for(re int i(1) ; i<=n ; ++i){
a[i] = read();
pos[i] = (i-1)/blocksize+1;
cnt[pos[i]][a[i]]++;
}
for(re int i(1) ; i<=tot ; ++i){
for(re int j(0) ; j<=c ; ++j){
cnt[i][j] += cnt[i-1][j];
}
}然后来看ans数组。
先枚举每一个块，枚举右端点，让ans[i][j]=ans[i][j?1]作为初始值，往后枚举块j的右端点，可以用一个桶来记录出现次数，具体看代码。
for(re int i(1) ; i<=tot ; ++i){
for(re int j(i) ; j<=tot ; ++j){
ans[i][j] = ans[i][j-1]; //赋值
for(re int k(l[j]) ; k<=r[j] ; ++k){
t[a[k]]++; //用桶来记录
if(!(t[a[k]]&1)) ans[i][j]++; //如果现在变为偶数个
else if(t[a[k]]!=1) ans[i][j]--; //从偶数变为奇数
}
}
memset(t,0,sizeof(t)); //别忘了每一次都要清空
}这时预处理两个重要的数据已经好了，来看如何分块。
分成???块，把每一个块的左端点和右端点先记录下来。
inline void init(){
blocksize = sqrt(n); //块大小
tot = (n-1)/blocksize+1; //块个数
for(re int i(1) ; i<=tot ; ++i){
l[i] = (i-1)*blocksize+1; //左端点
r[i] = i*blocksize; //右端点
}
r[tot] = n; //最后一个块的右端点设为n
}最后就是处理询问操作了。每次给定一个l和r，求该区间内偶数次数的个数。
分两种情况。如果两个端点在一个块中，直接暴力修改就行。
int idx=pos[ll],idy=pos[rr];
if(idy-idx<=1){
int res=0;
for(re int i(ll) ; i<=rr ; ++i){
t[a[i]]++;
if(!(t[a[i]]&1)) res++;
else if(t[a[i]]!=1) res--;
}
for(re int i(ll) ; i<=rr ; ++i) t[a[i]]--;
return res;
}第二种情况，如果两个块中间隔了很远，那么中间的块可以直接用预处理的ans数组，旁边的两个小块暴力询问。
int res = ans[idx+1][idy-1];
for(re int i(ll) ; i<=r[idx] ; ++i){
t[a[i]]++;
int pre=cnt[idy-1][a[i]]-cnt[idx][a[i]]; //大块中a[i]出现的次数
if(!((t[a[i]]+pre)&1)) res++; //从奇数变为偶数
else if(t[a[i]]+pre!=1) res--; //从偶数变为奇数
}
for(re int i(l[idy]) ; i<=rr ; ++i){
t[a[i]]++;
int pre=cnt[idy-1][a[i]]-cnt[idx][a[i]]; //跟上面一样
if(!((t[a[i]]+pre)&1)) res++;
else if(t[a[i]]+pre!=1) res--;
}
for(re int i(ll) ; i<=r[idx] ; ++i) t[a[i]]--; //最后别忘了清空
for(re int i(l[idy]) ; i<=rr ; ++i) t[a[i]]--; //而且只要清空这一段就行
return res;至此，这道题就做完啦。
总代码：
#include<bits/stdc++.h>
#define re register
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch == '-') f=-1 ; ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48) ; ch=getchar();}
return x*f;
}
inline void print(int x){
if(x/10) print(x/10);
putchar(x%10+'0');
}
const int M = 1e5+10;
int n,c,m;
int blocksize,tot,last=0;
int a[M],ans[350][350],cnt[350][M],l[M],r[M],pos[M],t[M];
inline void init(){
blocksize = sqrt(n);
tot = (n-1)/blocksize+1;
for(re int i(1) ; i<=tot ; ++i){
l[i] = (i-1)*blocksize+1;
r[i] = i*blocksize;
}
r[tot] = n;
}
inline int query(int ll,int rr){
int idx=pos[ll],idy=pos[rr];
if(idy-idx<=1){
int res=0;
for(re int i(ll) ; i<=rr ; ++i){
t[a[i]]++;
if(!(t[a[i]]&1)) res++;
else if(t[a[i]]!=1) res--;
}
for(re int i(ll) ; i<=rr ; ++i) t[a[i]]--;
return res;
}
else{
int res = ans[idx+1][idy-1];
for(re int i(ll) ; i<=r[idx] ; ++i){
t[a[i]]++;
int pre=cnt[idy-1][a[i]]-cnt[idx][a[i]];
if(!((t[a[i]]+pre)&1)) res++;
else if(t[a[i]]+pre!=1) res--;
}
for(re int i(l[idy]) ; i<=rr ; ++i){
t[a[i]]++;
int pre=cnt[idy-1][a[i]]-cnt[idx][a[i]];
if(!((t[a[i]]+pre)&1)) res++;
else if(t[a[i]]+pre!=1) res--;
}
for(re int i(ll) ; i<=r[idx] ; ++i) t[a[i]]--;
for(re int i(l[idy]) ; i<=rr ; ++i) t[a[i]]--;
return res;
}
}
signed main(){
n=read(),c=read(),m=read();
init();
for(re int i(1) ; i<=n ; ++i){
a[i] = read();
pos[i] = (i-1)/blocksize+1;
cnt[pos[i]][a[i]]++;
}
for(re int i(1) ; i<=tot ; ++i){
for(re int j(0) ; j<=c ; ++j){
cnt[i][j] += cnt[i-1][j];
}
}
for(re int i(1) ; i<=tot ; ++i){
for(re int j(i) ; j<=tot ; ++j){
ans[i][j] = ans[i][j-1];
for(re int k(l[j]) ; k<=r[j] ; ++k){
t[a[k]]++;
if(!(t[a[k]]&1)) ans[i][j]++;
else if(t[a[k]]!=1) ans[i][j]--;
}
}
memset(t,0,sizeof(t));
}
while(m--){
int ll,rr;
ll=read(),rr=read();
int L=(ll+last)%n+1,R=(rr+last)%n+1;
if(L > R) swap(L,R);
last = query(L,R);
printf("%d\n",last);
}
return 0;
}
