题目链接

题意：\(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\)，分出以下三种情况：

1. \(x\) 在 \([L_{l'+1},R_{r'-1}]\) 中出现次数为不为零的偶数，但是在 \([l,r]\) 中出现次数为奇数，则表明它被算在了 \(ans\) 中，但实际不符合条件，让 \(ans\) 减一

2. \(x\) 在 \([L_{l'+1},R_{r'-1}]\) 中出现次数奇数，但是在 \([l,r]\) 中出现次数为偶数，则表明它没有被算在了 \(ans\) 中，但实际符合条件，让 \(ans\) 加一

3. \(x\) 在 \([L_{l'+1},R_{r'-1}]\) 中没出现过，但是在 \([l,r]\) 中出现次数为偶数，让 \(ans\) 加 \(1\)。

   //Coded by tzc_wk
   /*
   数据不清空，爆零两行泪。
   多测不读完，爆零两行泪。
   边界不特判，爆零两行泪。
   贪心不证明，爆零两行泪。
   D P 顺序错，爆零两行泪。
   大小少等号，爆零两行泪。
   变量不统一，爆零两行泪。
   越界不判断，爆零两行泪。
   调试不注释，爆零两行泪。
   溢出不 l l，爆零两行泪。
   / #include 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('\n') #define space put(' ') #define y1 y_chenxiaoyan_1 #define y0 y_chenxiaoyan_0 typedef pair 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=x10+c-'0',c=getchar();
   return xneg; } 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=ansx%_MOD;
   x=xx%_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;
   }