lyd大神犇的狗粮题……
终于填掉了这个大坑， 之前由于有一些事情一直没有想清楚， 一直没有动手写此题，就记录一下那些“有一些事情”
1、对于对答案的贡献问题
若要统计[l, r]中所有颜色的贡献：
在扫描的过程中记录出现的次数cnt， 若cnt第一次变到2的时候， 把当前答案加一， 如果当前cnt大于二， 答案应当减一
**简单分析：**当一个数第一次到达出现2次的时候，应当显然地对答案产生了贡献， 当这个数在第三次出现的时候， 它之前产生的贡献就被消除了， 第四次出现的时候就又会被累加回来， 所以这样是对的
2、复杂度分析， 对于这样的块大小在块内不套log的情况下应当是取sqrt(n) 最优 （然而可能我太蒟了， 跑得很卡）
3、一开始犯了一个脑残的错误
pos[x] + 1 <= pos[y]
分分钟跑成暴力……
Code：
#include <cstdio> #include <cmath> using namespace std; const int N = 1e5 + 5; const int B = 320; int n, m, c, bnum, a[N], l[B], r[B], pos[N]; int sum[B][N], ans[B][B], cnt[N]; inline void read(int &X) { X = 0; char ch = 0; int op = 1; for(; ch > '9' || ch < '0'; ch = getchar()) if(ch == '-') op = -1; for(; ch >= '0' && ch <= '9'; ch = getchar()) X = (X << 3) + (X << 1) + ch - 48; X *= op; } inline void prework() { bnum = sqrt(n); for(int i = 1; i <= bnum; i++) { l[i] = (i - 1) * bnum + 1; r[i] = i * bnum; } if(r[bnum] < n) { bnum++; l[bnum] = r[bnum - 1] + 1; r[bnum] = n; } for(int i = 1; i <= bnum; i++) for(int j = l[i]; j <= r[i]; j++) { pos[j] = i; sum[i][a[j]]++; } for(int i = 1; i <= c; i++) for(int j = 1; j <= bnum; j++) sum[j][i] += sum[j - 1][i]; for(int i = 1; i <= bnum; i++) { int res = 0; for(int j = l[i]; j <= n; j++) { cnt[a[j]]++; if(cnt[a[j]] > 0 && cnt[a[j]] % 2 == 0) res++; else if(cnt[a[j]] > 2) res--; ans[i][pos[j]] = res; } for(int j = l[i]; j <= n; j++) cnt[a[j]]--; } } inline void swap(int &x, int &y) { int t = x; x = y; y = t; } int query(int x, int y) { int res = 0; if(pos[x] + 1 >= pos[y]) { for(int i = x; i <= y; i++) { cnt[a[i]]++; if(cnt[a[i]] > 0 && cnt[a[i]] % 2 == 0) res++; else if(cnt[a[i]] > 2) res--; } for(int i = x; i <= y; i++) cnt[a[i]]--; } else { /* for(int i = x; i <= r[pos[x]]; i++) cnt[a[i]]++; for(int i = l[pos[y]]; i <= y; i++) cnt[a[i]]++; */ res = ans[pos[x] + 1][pos[y] - 1]; for(int i = x; i <= r[pos[x]]; i++) { cnt[a[i]]++; int tmp = sum[pos[y] - 1][a[i]] - sum[pos[x]][a[i]] + cnt[a[i]]; /* if(tmp > 0) { if(tmp % 2 == 0) { if(cnt[a[i]] % 2 != 0) res--; } else { if(cnt[a[i]] % 2 != 0) res++; else res--; } } else { if(cnt[a[i]] > 0 && cnt[a[i]] % 2 == 0) res++; } */ if(tmp > 0 && tmp % 2 == 0) res++; else if(tmp > 2) res--; } for(int i = l[pos[y]]; i <= y; i++) { cnt[a[i]]++; int tmp = cnt[a[i]] + sum[pos[y] - 1][a[i]] - sum[pos[x]][a[i]]; /* if(tmp > 0) { if(tmp % 2 == 0) { if(cnt[a[i]] % 2 != 0) res--; } else { if(cnt[a[i]] % 2 != 0) res++; else res--; } } else { if(cnt[a[i]] > 0 && cnt[a[i]] % 2 == 0) res++; } */ if(tmp > 0 && tmp % 2 == 0) res++; else if(tmp > 2) res--; } for(int i = x; i <= r[pos[x]]; i++) cnt[a[i]]--; for(int i = l[pos[y]]; i <= y; i++) cnt[a[i]]--; } return res; } int main() { read(n), read(c), read(m); for(int i = 1; i <= n; i++) read(a[i]); prework(); for(int lastAns = 0, x, y; m--; ) { read(x), read(y); x = (x + lastAns) % n + 1, y = (y + lastAns) % n + 1; if(x > y) swap(x, y); printf("%d\n", lastAns = query(x, y)); } return 0; }