题目描述
给定正整数序列 ，你需要依次解决 m 个询问，每个询问用两个正整数 l-r 描述, 请求出有多少个数在 l-r 中出现正偶数次

输入第一行四个整数 n,c,m,t
第二行 n 个整数

强制在线

代码：

#include<bits/stdc++.h>
using namespace std;
int n,c,m,t,size;
int a[100005],ans;
int nex[100005],pre[100005],res[350][350],sav[350][100005];
int tot[100005],pos[350],top;
int main(){
	scanf("%d%d%d%d",&n,&c,&m,&t);
	size=(sqrt(n)+0.5);
	for(int i=size;i<=n;i+=size)pos[++top]=i;pos[top+1]=n+1;
	for(int i=1;i<=top;++i) {
		for(int j=pos[i-1]+1;j<=pos[i];++j)nex[j]=i;
		for(int j=pos[i];j<pos[i + 1];++j)pre[j]=i;
	}
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	for(int i=1;i<pos[1];i++)sav[1][a[i]]++;
	for(int i=2;i<=top;i++){
		memcpy(sav[i],sav[i-1],sizeof(sav[i]));
		for(int j=pos[i-1];j<pos[i];j++)sav[i][a[j]]++;
	}
	for(int i=1;i<=top;i++){
		ans=0;memset(tot,0,sizeof(tot));
		for(int j=i+1;j<=top;++j){
			for(int k=pos[j-1];k<pos[j];++tot[a[k++]]) {
	    		tot[a[k]]&1?++ans:(tot[a[k]]?--ans: 0);
			}
			res[i][j]=ans;
		}
	}
	
	ans=0;memset(tot,0,sizeof(tot));
	for(int i=1,x,y,t,L,R;i<=m;i++) {
		scanf("%d%d",&x,&y);
		x=(x+t*ans)%n+1,y=(y+t*ans)%n+1;
		if(x>y)swap(x,y);
		if(y-x+1<=(size<<1)){
			ans=0;
			for(int j=x;j<=y;++tot[a[j++]])tot[a[j]]&1?++ans:(tot[a[j]]?--ans:0);
			
			for(int j=x;j<=y;++j)--tot[a[j]];
			printf("%d\n",ans);continue;
		}
		L=nex[x],R=pre[y];ans=res[L][R];
		for(int j=x;j<pos[L];++tot[a[j++]]){
			t=tot[a[j]]+sav[R][a[j]]-sav[L][a[j]];
			t&1?++ans:(t?--ans:0);
		}
		for(int j=pos[R];j<=y;++tot[a[j++]]){
			t=tot[a[j]]+sav[R][a[j]]-sav[L][a[j]];
			t&1?++ans:(t?--ans:0);
		}
		for(int j=x;j<pos[L];++j)--tot[a[j]];
		for(int j=pos[R];j<=y;++j)--tot[a[j]];
		printf("%d\n",ans);
	}
	
	
	return 0;
} 

std:

#include <cstdio>
#include <cmath>
#include <cstring>

#define RR register
#define Get() (Ch = getchar())
inline int Fastin() {
	RR int N; RR char Ch;
	for(Get(); Ch < 48; Get()); N = Ch ^ 48;
	for(Get(); Ch > 47; Get()) N = (N << 3) + (N << 1) + (Ch ^ 48);
	return N;
}

#define MaxB 350
#define MaxN 100010
#define Pos(_) (_ * Siz)
#define Bl(_) (_ / Siz)
int N, M, C, T, Siz, tot, A[MaxN], Pos[MaxB], Nex[MaxN], Pre[MaxN];
int Ans[MaxB][MaxB], Sav[MaxB][MaxN], Buc[MaxN];

int main(void) {
//	freopen("count.in","r",stdin) ;
//	freopen("count.out","w",stdout);	
	N = Fastin(), C = Fastin(), M = Fastin(), T = Fastin();
	Siz = int(sqrt(N) + 0.5);
	
	for(RR int i = Siz; i <= N; i += Siz) Pos[++tot] = i; Pos[tot + 1] = N + 1;
	
	for(RR int i = 1; i <= tot; ++i) {
		for(RR int j = Pos[i - 1] + 1; j <= Pos[i]; ++j) Nex[j] = i;
		for(RR int j = Pos[i]; j < Pos[i + 1]; ++j) Pre[j] = i;
	}
	
	for(RR int i = 1; i <= N; ++i) A[i] = Fastin();
	for(RR int i = 1; i < Pos[1]; ++i) Sav[1][A[i]]++;
	for(RR int i = 2; i <= tot; ++i){
		memcpy(Sav[i], Sav[i - 1], (C + 1) << 2);
		for(RR int j = Pos[i - 1]; j < Pos[i]; ++j) Sav[i][A[j]]++;
	} 
	
	for(RR int i = 1, Now; i <= tot; ++i) {
		memset(Buc, 0, (C + 1) << 2), Now = 0;
		for(RR int j = i + 1; j <= tot; ++j) {
			for(RR int k = Pos[j - 1]; k < Pos[j]; ++Buc[A[k++]]) {
				Buc[A[k]] & 1? ++Now: (Buc[A[k]]? --Now: 0); 
			}
			Ans[i][j] = Now;
		}
	}
	
//	for(int i=1;i<=tot;i++)for(int j=i+1;j<=tot;j++)printf("%d ",Ans[i][j]);
//	puts("");
	for(RR int i = 1, x, y, t, Las = 0, L, R; i <= M; ++i) {
		x = Fastin(), y = Fastin();
		x = (x + Las * T) % N + 1, y = (y + Las * T) % N + 1;
		if(x > y) t = x, x = y, y = t;
		if(y - x + 1 <= (Siz << 1)) {
			Las = 0;
			for(RR int j = x; j <= y; ++Buc[A[j++]]) {
				Buc[A[j]] & 1? ++Las: (Buc[A[j]]? --Las: 0);
			}
			for(RR int j = x; j <= y; ++j)--Buc[A[j]];
			printf("%d\n",Las);continue;
		}
		L = Nex[x], R = Pre[y], Las = Ans[L][R];
		for(RR int j = x; j < Pos[L]; ++Buc[A[j++]]) {
			t = Buc[A[j]] + Sav[R][A[j]] - Sav[L][A[j]];
			t & 1? ++Las: (t? --Las: 0);
		}
		for(RR int j = Pos[R]; j <= y; ++Buc[A[j++]]) {
			t = Buc[A[j]] + Sav[R][A[j]] - Sav[L][A[j]];
			t & 1? ++Las: (t? --Las: 0);
		}
		for(RR int j = x; j < Pos[L]; ++j) --Buc[A[j]];
		for(RR int j = Pos[R]; j <= y; ++j) --Buc[A[j]];
		printf("%d\n", Las);
	}
	
	return 0;
}