[文章目录]
Description
N个数，M组询问，每次问[l,r]中有多少个数出现正偶数次。n,m<=10^5
统计整块的答案，之后零散的部分再分情况计算变化即可。
#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 100100
inline char nc()
{
static char buf[100000],*p1,*p2;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
int x=0; char ch=nc();
while(!isdigit(ch)) ch=nc();
while(isdigit(ch)) x=x*10+(ch^'0'),ch=nc();
return x;
}
int n,m,c,bl,a[N],t[N],z[N];
int f[320][320],g[N][320];
int main()
{
n=read(); c=read(); m=read();
int i; bl=(int)sqrt(n)+1;
for(i=0;i<n;++i) a[i]=read();
int l,r,now;
for(l=0;l<n;l+=bl)
{
memset(t,0,sizeof t);
for(now=0,r=l+bl-1,i=l;i<n;++i)
{
if(t[a[i]]&1) now++;
else if(t[a[i]]) now--;
t[a[i]]++;
if(i==r) f[l/bl][r/bl]=now,r+=bl;
}
}
memset(t,0,sizeof t);
for(l=0,r=bl-1;l<n;++l)
{
t[a[l]]++;
if(l==r) for(r+=bl,i=1;i<=c;++i) g[i][l/bl]=t[i];
}
memset(t,0,sizeof t);
int L,R,top,x,ans=0;
while(m--)
{
l=(read()+ans)%n; r=(read()+ans)%n;
if(l>r) swap(l,r);
if(r-l+1<=bl*2)
{
for(ans=0,i=l;i<=r;++i)
{
if(t[a[i]]&1) ans++;
else if(t[a[i]]) ans--;
t[a[i]]++;
}
printf("%d\n",ans);
for(i=l;i<=r;++i) t[a[i]]=0;
}
else
{
L= l%bl==0 ? l/bl : l/bl+1;
R= r%bl==bl-1 ? r/bl : r/bl-1;
for(top=0,i=l;i%bl!=0;++i)
{
if(!t[a[i]]) z[++top]=a[i];
t[a[i]]++;
}
for(i=r;i%bl!=bl-1;--i)
{
if(!t[a[i]]) z[++top]=a[i];
t[a[i]]++;
}
ans=f[L][R];
for(i=1;i<=top;++i)
{
x= L ? g[z[i]][R]-g[z[i]][L-1] : g[z[i]][R];
if(t[z[i]]&1)
{
if(!(x&1)&&x) ans--;
else if(x&1) ans++;
}
else ans+=!x;
}
printf("%d\n",ans);
for(i=1;i<=top;++i) t[z[i]]=0;
}
}
return 0;
}