分块——暴力统计
搞了4个多小时才好不容易把这题A了，虽然luogu加O2过的，但bzoj是过了的
虽然跑的比较慢但觉得方法很好理解，一开始有些细节没考虑以及预处理比较慢，就没过。之后借鉴了黄学长的代码才弄出来
不嫌弃的话就看看吧
思路
这题和蒲公英其实是处理方法很相近的，别看是黑题，其实是板子
主要是预处理每个大块之间出现偶数次的数的个数
注意O(n)预处理，O(n2)肯定不行
查询的时候需要注意在处理零散块时也要统计一遍
要注意分奇偶考虑，在考虑零散块的时候也要考虑大块中的出现次数奇偶性。
例：在1-2中出现2次，2-6中出现3次，没有被统计过要加答案；
在1-2中出现1次，2-6出现2次，这时一共出现3次就不符合了，答案反而要减
这是非常需要注意的，所以细节的处理也非常重要所以直接看代码吧
我用的vector估计比较慢，query写的也很繁复，这估计就是luogu TLE的原因吧，只有O2才能救我，但只觉得这样思路很清晰就这样写了
这题c给的真的有用吗emmmmmmm
代码
#include <bits/stdc++.h>
#define N 100005
#define ri register int
using namespace std;
int bl[N],l[N],r[N],n,p,a[N],cnt,val[N],m,num,vis2[N];
int f[1505][1505];//预处理每个大块l,r之间的出现次数为偶数次的个数
vector<int>ve[N];
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*10+ch-'0';ch=getchar();}
return x*f;
}
int vis[N];
inline void pre()//预处理
{
for(ri i=1;i<=bl[n];i++)
{
int ans=0;
for(ri j=l[i];j<=n;j++)vis[a[j]]=0;
for(ri j=l[i];j<=n;j++)
{
if(!(vis[a[j]]&1)&&vis[a[j]])ans--;//如果在之前已经出现过偶数次了，说明此时这个数已经不符合要求，ans--
vis[a[j]]++;
if(!(vis[a[j]]&1))ans++;//此时满足偶数次，ans++
f[i][bl[j]]=ans;//边算边更新就不用n2了，我之前n2写法就很慢
}
}
}
inline int two_point(int x,int y,int v)//二分求在x-y区间出现的次数，不知道手写二分会不会快一些QWQ
{
int t=upper_bound(ve[v].begin(),ve[v].end(),y)-lower_bound(ve[v].begin(),ve[v].end(),x);
return t;
}
inline int query(int x,int y)//这部分可能我写的也比较慢，但还是比较好理解的
{
int ans=0,mx;
int L=bl[x],R=bl[y];
if(L==R)//当在同一个块时，直接暴力统计
{
for(ri i=x;i<=y;i++)
{
int t=two_point(x,y,a[i]);
if(!(t&1)&&!vis2[a[i]])ans++,vis2[a[i]]=1;
}
for(ri i=x;i<=y;i++)vis2[a[i]]=0;//清零
}
else
{
ans=f[L+1][R-1];//先计算出中间块的满足条件的数的个数
int ll=l[L+1];int rr=r[R-1];
for(ri i=x;i<=r[L];i++)
{
if(vis2[a[i]])continue;
int t=two_point(x,y,a[i]),t2=two_point(ll,rr,a[i]);
if(!(t&1))//如果在散区间中出现次数为偶数次
{if((t2&1)||!t2)ans++;}//如果在大块中出现奇数次或没出现，（之前也没统计过，此时满足条件，ans++
else if(!(t2&1)&&t2)ans--;//如果散区间出现奇数次，大块中出现偶数次且之前统计过，此时已经不满足条件，ans--
vis2[a[i]]=1;
}
for(ri i=l[R];i<=y;i++)//同上
{
if(vis2[a[i]])continue;
int t=two_point(x,y,a[i]),t2=two_point(ll,rr,a[i]);
if(!(t&1))
{if((t2&1)||!t2)ans++;}
else if(!(t2&1)&&t2)ans--;
vis2[a[i]]=1;
}
for(ri i=x;i<=r[L];i++) vis2[a[i]]=0;
for(ri i=l[R];i<=y;i++)vis2[a[i]]=0;
}
return ans;
}
int main()
{
n=read();num=read();m=read();
p=sqrt((double)n/log((double)n)*log(2));
for(ri i=1;i<=n;i++)//预处理
{
a[i]=read();
ve[a[i]].push_back(i);//用vector处理每个数字出现的位置，因为是递增的可以直接二分，所以我选择了vector而不是数组
bl[i]=(i-1)/p+1;
if(l[bl[i]]==0)l[bl[i]]=i;
r[bl[i]]=i;
}
pre();
int pre_ans=0;
for(ri i=1;i<=m;i++)
{
int x,y;
x=read();y=read();
x=(x+pre_ans)%n+1;
y=(y+pre_ans)%n+1;
if(x>y)swap(x,y);
pre_ans=query(x,y);
printf("%d\n",pre_ans);
}
return 0;
}
感谢