题目
分析
首先此题好像用不了线段树什么的，只好考虑分块
但是分块这种题目其实看注释会更好啊，时间复杂度 O ( n n ) O(n\sqrt n) O(nn
)
代码
#include <cstdio>
#include <cctype>
#include <cmath>
#define rr register
using namespace std;
const int N=100011;
//dp表示块的答案，s表示从某个块的开头到末尾某个种类的个数
int n,m,block,a[N],le[N],cnt[N],st[N],s[318][N],dp[318][318],pos[N],top;
inline signed iut(){
rr int ans=0; rr char c=getchar();
while (!isdigit(c)) c=getchar();
while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
return ans;
}
inline void print(int ans){
if (ans>9) print(ans/10);
putchar(ans%10+48);
}
inline signed pro(int l,int r){
rr int ans=0;
if (pos[l]+1<=pos[r]-1) ans=dp[pos[l]+1][pos[r]-1];
for (rr int i=l;i<le[pos[l]+1];++i) ++cnt[a[i]],st[++top]=a[i];
for (rr int i=le[pos[r]];i<=r;++i) ++cnt[a[i]],st[++top]=a[i];
for (;top;--top){
rr int x=st[top];
if (cnt[x]){
if (!(s[pos[l]+1][x]^s[pos[r]][x])) ans+=(cnt[x]&1)^1;//该种类在中间的大块里没有出现
else if (cnt[x]&1) ans+=((s[pos[l]+1][x]^s[pos[r]][x])&1)?1:-1;//偶数加1，奇数减1
cnt[x]=0;
}
}
return ans;
}
signed main(){
n=iut(); iut(); m=iut(); block=sqrt(n);
for (rr int i=1;i<=n;++i){//分段
a[i]=iut(),pos[i]=(i-1)/block+1;
if (pos[i]^pos[i-1]) le[pos[i]]=i;
}
pos[n+1]=pos[n]+1,le[pos[n+1]]=n+1;
for (rr int i=1;i<=pos[n];++i){
rr int now=0;
for (rr int j=le[i];j<=n;++j){
++s[i][a[j]];
if ((s[i][a[j]]&1)&&(s[i][a[j]]^1)) --now;//奇数个
else if (!(s[i][a[j]]&1)) ++now;//正偶数个
if (pos[j]^pos[j+1]) dp[i][pos[j]]=now;
}
}
for (rr int ans=0,l,r;m;--m){
l=(iut()+ans)%n+1,r=(iut()+ans)%n+1;
if (l>r) l^=r,r^=l,l^=r; ans=top=0;
if (pos[l]^pos[r]) ans=pro(l,r);
else{
for (rr int i=l;i<=r;++i) ++cnt[a[i]],st[++top]=a[i];
for (;top;--top) if (cnt[st[top]])
ans+=(cnt[st[top]]&1)^1,cnt[st[top]]=0;//暴力
}
print(ans); putchar(10);
}
return 0;
}