题意：(n) 个数，每个数都在 ([1,c]) 中，(m) 次询问，每次问在 ([l,r]) 中有多少个数出现偶数次。强制在线。
(1 leq n,m,c leq 10^5)
如果不强制在线的话可以想到莫队，关键这个强制在线怎么处理。
很容易想到对原数列进行根号分块，为了方便表示，定义 (L_i) 为第 (i) 块的左端点，(R_i) 为第 (i) 块的右端点。
我们记 (t_{i,j}) 表示在 ([L_i,n]) 中 (j) 这个数出现了多少次，(f_{i,j}) 表示在 ([L_i,R_j]) 有多少个数出现次数为偶数。
我还是太 naive 了，一看到这个“区间”就想着用区间 dp 的方式进行转移，复杂度爆炸。
事实上，我们可以在求出 (t) 的同时求出 (f)。枚举起点块 (i)，定义 (num) 记录有多少个数出现了偶数次，一边往后扫一遍更新 (num)。
查询区间 ([l,r]) 的时候，如果 (l,r) 在同一块中，直接暴力查找就行了。
如果 ([l,r]) 不在同一块中，记 (l') 为 (l) 所在的块，(r') 为 (r) 所在的块，那么我们先将 (ans) 赋值为 (f_{l'+1,r'-1})，然后对于 ([l,R_{l'}] cup [L_{r'},r]) 中所有不同的数 (x)，分出以下三种情况：
- (x) 在 ([L_{l'+1},R_{r'-1}]) 中出现次数为不为零的偶数，但是在 ([l,r]) 中出现次数为奇数，则表明它被算在了 (ans) 中，但实际不符合条件，让 (ans) 减一
- (x) 在 ([L_{l'+1},R_{r'-1}]) 中出现次数奇数，但是在 ([l,r]) 中出现次数为偶数，则表明它没有被算在了 (ans) 中，但实际符合条件，让 (ans) 加一
- (x) 在 ([L_{l'+1},R_{r'-1}]) 中没出现过，但是在 ([l,r]) 中出现次数为偶数，让 (ans) 加 (1)。
//Coded by tzc_wk
/*
数据不清空，爆零两行泪。
多测不读完，爆零两行泪。
边界不特判，爆零两行泪。
贪心不证明，爆零两行泪。
D P 顺序错，爆零两行泪。
大小少等号，爆零两行泪。
变量不统一，爆零两行泪。
越界不判断，爆零两行泪。
调试不注释，爆零两行泪。
溢出不 l l，爆零两行泪。
*/
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define fz(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
#define foreach(it,v) for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define all(a) a.begin(),a.end()
#define giveup(...) return printf(__VA_ARGS__),0;
#define fill0(a) memset(a,0,sizeof(a))
#define fill1(a) memset(a,-1,sizeof(a))
#define fillbig(a) memset(a,0x3f,sizeof(a))
#define fillsmall(a) memset(a,0xcf,sizeof(a))
#define mask(a) (1ll<<(a))
#define maskx(a,x) ((a)<<(x))
#define _bit(a,x) (((a)>>(x))&1)
#define _sz(a) ((int)(a).size())
#define filei(a) freopen(a,"r",stdin);
#define fileo(a) freopen(a,"w",stdout);
#define fileio(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)
#define eprintf(...) fprintf(stderr,__VA_ARGS__)
#define put(x) putchar(x)
#define eoln put('
')
#define space put(' ')
#define y1 y_chenxiaoyan_1
#define y0 y_chenxiaoyan_0
typedef pair<int,int> pii;
inline int read(){
int x=0,neg=1;char c=getchar();
while(!isdigit(c)){
if(c=='-') neg=-1;
c=getchar();
}
while(isdigit(c)) x=x*10+c-'0',c=getchar();
return x*neg;
}
inline void print(int x){
if(x<0){
putchar('-');
print(abs(x));
return;
}
if(x<=9) putchar(x+'0');
else{
print(x/10);
putchar(x%10+'0');
}
}
inline int qpow(int x,int e,int _MOD){
int ans=1;
while(e){
if(e&1) ans=ans*x%_MOD;
x=x*x%_MOD;
e>>=1;
}
return ans;
}
const int BLOCK_SZ=320;
int n=read(),c=read(),m=read(),a[100005],cnt[322][100005],sum[322][322];
int blk,L[322],R[322],bel[100005];
int vis[100005];
inline void prework(){
blk=(n-1)/BLOCK_SZ+1;
fz(i,1,blk){
L[i]=(i-1)*BLOCK_SZ+1;
R[i]=min(i*BLOCK_SZ,n);
fz(j,L[i],R[i]){
bel[j]=i;
}
}
fz(i,1,blk){
int num=0;
fill0(vis);
fz(j,L[i],n){
cnt[i][a[j]]++;
if(!vis[a[j]]) vis[a[j]]=1,num++;
if(cnt[i][a[j]]&1) num--;
else num++;
if(bel[j]!=bel[j+1]) sum[i][bel[j]]=num;
}
}
}
int cntt[100005];
inline int query(int l,int r){
if(bel[l]==bel[r]){
int ans=0;
fz(i,l,r) cntt[a[i]]++;
fz(i,l,r){
if(!vis[a[i]]){
if(cntt[a[i]]&1^1) ans++;
vis[a[i]]=1;
}
}
fz(i,l,r) cntt[a[i]]--,vis[a[i]]=0;
return ans;
}
else{
int l0=bel[l],r0=bel[r];
fz(i,l,R[l0]) cntt[a[i]]++;
fz(i,L[r0],r) cntt[a[i]]++;
int ans=sum[l0+1][r0-1];
fz(i,l,R[l0]){
if(!vis[a[i]]){
if((cnt[l0+1][a[i]]-cnt[r0][a[i]])>0){
if(((cntt[a[i]]+cnt[l0+1][a[i]]-cnt[r0][a[i]])&1^1)&&(cnt[l0+1][a[i]]-cnt[r0][a[i]])&1)
ans++;
if(((cntt[a[i]]+cnt[l0+1][a[i]]-cnt[r0][a[i]])&1)&&(cnt[l0+1][a[i]]-cnt[r0][a[i]])&1^1)
ans--;
}
else{
if((cntt[a[i]]&1)^1) ans++;
}
vis[a[i]]=1;
}
}
fz(i,L[r0],r){
if(!vis[a[i]]){
if((cnt[l0+1][a[i]]-cnt[r0][a[i]])>0){
if(((cntt[a[i]]+cnt[l0+1][a[i]]-cnt[r0][a[i]])&1^1)&&(cnt[l0+1][a[i]]-cnt[r0][a[i]])&1)
ans++;
if(((cntt[a[i]]+cnt[l0+1][a[i]]-cnt[r0][a[i]])&1)&&(cnt[l0+1][a[i]]-cnt[r0][a[i]])&1^1)
ans--;
}
else{
if(cntt[a[i]]&1^1) ans++;
}
vis[a[i]]=1;
}
}
fz(i,l,R[l0]) cntt[a[i]]--,vis[a[i]]=0;
fz(i,L[r0],r) cntt[a[i]]--,vis[a[i]]=0;
return ans;
}
}
signed main(){
fz(i,1,n) a[i]=read();
prework();
fill0(vis);
int anss=0;
while(m--){
int l=read(),r=read();
l=(l+anss)%n+1,r=(r+anss)%n+1;
if(l>r) swap(l,r);
anss=query(l,r);
cout<<anss<<endl;
}
return 0;
}