听说这是一道虐狗题（大雾
题目要求每次询问一段区间之内有多少个数出现了偶数次。我们故技重施，使用分块去解决。和求区间众数很相似，先预处理出每个数在前i个块中出现过多少次，之后预处理出块i到块j有多少个元素出现过正偶数次。做过上一道题应该觉得这个很简单了……
查询的时候，对于整块区间先取出出现正偶数次的元素个数，对于每个零散元素，统计出现次数和在整块内的出现次数，之后通过奇偶性比较来确定一共有多少元素出现在区间之内即可。
但是这道题强力卡常，一开始用O2没什么感觉，去掉O2一开始20，改成不用memset70，再优化一些勉强80，实在卡不过去了，只能开O2，还是跑的不错的。
看一下代码。
// luogu-judger-enable-o2 #include<cstdio> #include<algorithm> #include<cstring> #include<iostream> #include<cmath> #include<set> #include<queue> #define rep(i,a,n) for(register int i = a;i <= n;i++) #define per(i,n,a) for(register int i = n;i >= a;i--) #define enter putchar(' ') using namespace std; typedef long long ll; const int M = 100005; const int N = 320; const int INF = 1000000009; inline int read() { int ans = 0,op = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') op = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { ans *= 10; ans += ch - '0'; ch = getchar(); } return ans * op; } inline void write(int x) { if(x < 0) x = -x,putchar('-'); if(x >= 10) write(x / 10); putchar(x % 10 + '0'); } int n,c,m,B,blo[M],sum[N][M],l[N],r[N],cnt,even[N][N],sta[M],top,cur[M],a[M],last,g = 1,now,x,y; void clear() { while(top) cur[sta[top]] = 0,top--; } inline void init() { rep(i,1,cnt) { rep(j,1,c) { if(!sum[i-1][j]) continue; sum[i][j] += sum[i-1][j]; } rep(j,l[i],r[i]) sum[i][a[j]]++; } rep(i,1,cnt) { now = 0,g = i; rep(j,l[i],n) { if(!cur[a[j]]) sta[++top] = a[j]; cur[a[j]]++; if((cur[a[j]] & 1) && cur[a[j]] != 1) now--; else if(!(cur[a[j]] & 1)) now++; if(j == r[g]) even[i][g] = now,g++; } clear(); } } int query(int x,int y) { int L = blo[x],R = blo[y]; clear(); now = 0; if(L == R) { rep(i,x,y) { if(!cur[a[i]]) sta[++top] = a[i]; cur[a[i]]++; if(cur[a[i]] & 1 && cur[a[i]] != 1) now--; else if(!(cur[a[i]] & 1)) now++; } return now; } now = even[L+1][R-1]; rep(i,x,r[L]) { if(!cur[a[i]]) sta[++top] = a[i]; cur[a[i]]++; } rep(i,l[R],y) { if(!cur[a[i]]) sta[++top] = a[i]; cur[a[i]]++; } while(top) { int k = sta[top],p = sum[R-1][k] - sum[L][k]; if((cur[k] & 1) && (!(p & 1)) && p != 0) now--; else if((cur[k] & 1) && (p & 1)) now++; else if(!(cur[k] & 1) && p == 0) now++; cur[k] = 0,top--; } return now; } int main() { n = read(),c = read(),m = read(),B = sqrt(n); cnt = (n % B) ? n / B + 1 : n / B; rep(i,1,cnt) l[i] = r[i-1] + 1,r[i] = l[i] + B - 1; r[cnt] = n; rep(i,1,n) { blo[i] = g; if(i == r[g]) g++; } rep(i,1,n) a[i] = read(); init(); rep(i,1,m) { x = read() + last + 1,y = read() + last + 1; if(x > n) x -= n; if(y > n) y -= n; if(x > y) x ^= y ^= x ^= y; last = query(x,y); write(last),enter; } return 0; }