郑重声明：我的前几到分块题写法上都有点小毛病，以这篇为主！
这道题感觉也是分块的基本套路，只不过卡常，得开氧气。
维护俩：sum[i][j]表示前 i 块中，数字 j 出现了多少次，ans[i][j]表示块 i 到块 j 的答案。这两者都可以在O(n√n)内预处理。方法也比较套路，具体看代码。
查询的时候也很套路，多开一个num[i]，表示 i 这个数在零散部分出现了多少次，那么num[i] + sum[r - 1][i] - sum[l][i]就是在[L, R]中出现了多少次。
因为卡常，所以别用memset，开一个数组记录存了那些数，然后逐个清零即可。
1 #include<cstdio> 2 #include<iostream> 3 #include<cmath> 4 #include<algorithm> 5 #include<cstring> 6 #include<cstdlib> 7 #include<cctype> 8 #include<vector> 9 #include<stack> 10 #include<queue> 11 using namespace std; 12 #define enter puts("") 13 #define space putchar(' ') 14 #define Mem(a, x) memset(a, x, sizeof(a)) 15 #define rg register 16 typedef long long ll; 17 typedef double db; 18 const int INF = 0x3f3f3f3f; 19 const db eps = 1e-8; 20 const int maxn = 1e5 + 5; 21 const int maxb = 320; 22 inline ll read() 23 { 24 ll ans = 0; 25 char ch = getchar(), last = ' '; 26 while(!isdigit(ch)) {last = ch; ch = getchar();} 27 while(isdigit(ch)) {ans = (ans << 1) + (ans << 3) + ch - '0'; ch = getchar();} 28 if(last == '-') ans = -ans; 29 return ans; 30 } 31 inline void write(ll x) 32 { 33 if(x < 0) x = -x, putchar('-'); 34 if(x >= 10) write(x / 10); 35 putchar(x % 10 + '0'); 36 } 37 38 int n, c, m, a[maxn]; 39 int S, Cnt = 0, blo[maxn], lb[maxb], rb[maxb]; 40 int sum[maxb][maxn], ans[maxb][maxb]; 41 int num[maxn], cnt[maxn], cn = 0; 42 void init() 43 { 44 S = sqrt(n); 45 Cnt = n % S ? n / S + 1: n / S; 46 for(int i = 1; i <= Cnt; ++i) lb[i] = rb[i - 1] + 1, rb[i] = lb[i] + S - 1; //这里以前的写法不对 47 rb[Cnt] = n; 48 for(int i = 1, j = 1; i <= n; ++i) blo[i] = j, j += (i == rb[j]); 49 for(int i = 1; i <= Cnt; ++i) 50 { 51 for(int j = 1; j <= c; ++j) sum[i][j] += sum[i - 1][j]; 52 for(int j = lb[i]; j <= rb[i]; ++j) sum[i][a[j]]++; 53 } 54 for(int i = 1; i <= Cnt; ++i) 55 { 56 int tot = 0; 57 for(int j = lb[i], k = i; j <= n; ++j) 58 { 59 if(!num[a[j]]) cnt[++cn] = a[j]; 60 if(++num[a[j]] > 1) 61 { 62 if(num[a[j]] & 1) tot--; 63 else tot++; 64 } 65 if(j == rb[k]) ans[i][k++] = tot; 66 } 67 while(cn) num[cnt[cn]] = 0, cn--; 68 } 69 } 70 int query(int L, int R) 71 { 72 int l = blo[L], r = blo[R], ret = 0; 73 if(l == r) 74 { 75 for(int i = L; i <= R; ++i) 76 { 77 if(!num[a[i]]) cnt[++cn] = a[i]; 78 if(++num[a[i]] > 1) 79 { 80 if(num[a[i]] & 1) ret--; 81 else ret++; 82 } 83 } 84 while(cn) num[cnt[cn]] = 0, cn--; 85 return ret; 86 } 87 ret = ans[l + 1][r - 1]; 88 for(int i = L; i <= rb[l]; ++i) 89 { 90 if(!num[a[i]]) cnt[++cn] = a[i]; 91 num[a[i]]++; 92 int tp = num[a[i]] + sum[r - 1][a[i]] - sum[l][a[i]]; 93 if(tp > 1) 94 { 95 if(tp & 1) ret--; 96 else ret++; 97 } 98 } 99 for(int i = lb[r]; i <= R; ++i) 100 { 101 if(!num[a[i]]) cnt[++cn] = a[i]; 102 num[a[i]]++; 103 int tp = num[a[i]] + sum[r - 1][a[i]] - sum[l][a[i]]; 104 if(tp > 1) 105 { 106 if(tp & 1) ret--; 107 else ret++; 108 } 109 } 110 while(cn) num[cnt[cn]] = 0, cn--; 111 return ret; 112 } 113 114 int Ans = 0; 115 116 int main() 117 { 118 n = read(), c = read(), m = read(); 119 for(int i = 1; i <= n; ++i) a[i] = read(); 120 init(); 121 for(int i = 1; i <= m; ++i) 122 { 123 int L = read(), R = read(); 124 L = (L + Ans) % n + 1; R = (R + Ans) % n + 1; if(L > R) swap(L, R); 125 Ans = query(L, R); 126 write(Ans), enter; 127 } 128 return 0; 129 }