题意：[l,r]之间有多少个数出现了正偶数次。强制在线。
解：第一眼想到莫队，然后发现强制在线...分块吧。
有个很朴素的想法就是蒲公英那题的套路，做每块前缀和的桶。
然后发现这题空间128M，数组大小我的是133M......看到有人卡到了122M，但是我又不想冒险，就换写法了。(题解里全是空间n1.5的...)
那就用蒲公英的另一个套路吧。。。vector + 二分。
预处理出每两个块之间的答案，然后查询的时候对边角扫一遍，每个数vector二分，求得出现几次，统计答案。
这样一来块大小是(n/logn)0.5的，然后交上去发现T成10分...自闭了。
YY出了个做法，每个数维护是第几个出现的该数值的数，然后发现对于某种数值只出现在一边边角的话，不会处理，又只会vector了...虽然还可以值域分块做到log(n0.5)，但是感觉上没啥太大优化，懒得写了...
把之前的10分代码玄学调了一波块大小，然后吸氧，居然A了。。。。。。自闭了。
1 // luogu-judger-enable-o2 2 #include <cstdio> 3 #include <algorithm> 4 #include <vector> 5 #include <cmath> 6 7 const int N = 100010; 8 9 int bin[N], a[N], sum[1400][1400], n, lm, le[N], re[N], fr[N]; 10 std::vector<int> v[N]; 11 bool vis[N]; 12 13 inline void read(int &x) { 14 x = 0; 15 char c = getchar(); 16 while(c < '0' || c > '9') { 17 c = getchar(); 18 } 19 while(c >= '0' && c <= '9') { 20 x = (x << 3) + (x << 1) + c - 48; 21 c = getchar(); 22 } 23 return; 24 } 25 26 inline int getTime(int x, int y, int c) { 27 if(x > y) { 28 return 0; 29 } 30 x = std::lower_bound(v[c].begin(), v[c].end(), x) - v[c].begin(); 31 y = std::upper_bound(v[c].begin(), v[c].end(), y) - v[c].begin() - 1; 32 return y - x + 1; 33 } 34 35 inline int ask(int x, int y) { 36 int l = fr[x], r = fr[y], ans = 0; 37 if(l == r) { 38 for(int k = x; k <= y; k++) { 39 if(bin[a[k]]) { 40 bin[a[k]] & 1 ? ans++ : ans--; 41 } 42 bin[a[k]]++; 43 } 44 for(int k = x; k <= y; k++) { 45 bin[a[k]]--; 46 } 47 return ans; 48 } 49 for(int k = x; k <= re[l]; k++) { 50 bin[a[k]]++; 51 } 52 for(int k = le[r]; k <= y; k++) { 53 bin[a[k]]++; 54 } 55 for(int k = x; k <= re[l]; k++) { 56 if(vis[a[k]]) { 57 continue; 58 } 59 vis[a[k]] = 1; 60 if(bin[a[k]] & 1) { 61 int t = getTime(le[l + 1], re[r - 1], a[k]); 62 if(t) { 63 ans += t & 1 ? 1 : -1; 64 } 65 } 66 else { 67 ans += getTime(le[l + 1], re[r - 1], a[k]) == 0; 68 } 69 } 70 for(int k = le[r]; k <= y; k++) { 71 if(vis[a[k]]) { 72 continue; 73 } 74 vis[a[k]] = 1; 75 if(bin[a[k]] & 1) { 76 int t = getTime(le[l + 1], re[r - 1], a[k]); 77 if(t) { 78 ans += t & 1 ? 1 : -1; 79 } 80 } 81 else { 82 ans += getTime(le[l + 1], re[r - 1], a[k]) == 0; 83 } 84 } 85 for(int k = x; k <= re[l]; k++) { 86 vis[a[k]] = 0; 87 bin[a[k]]--; 88 } 89 for(int k = le[r]; k <= y; k++) { 90 vis[a[k]] = 0; 91 bin[a[k]]--; 92 } 93 return ans + sum[l + 1][r - 1]; 94 } 95 96 int main() { 97 int m; 98 read(n); 99 read(lm); 100 read(m); 101 int T = sqrt((double)(n) / log2(n) * 2); 102 for(int i = 1; i <= n; i++) { 103 read(a[i]); 104 v[a[i]].push_back(i); 105 fr[i] = (i - 1) / T + 1; 106 } 107 // prework 108 for(int i = 1; i <= fr[n]; i++) { 109 le[i] = re[i - 1] + 1; 110 re[i] = le[i] + T - 1; 111 if(i == fr[n]) { 112 re[i] = n; 113 } 114 } 115 116 for(int l = 1; l <= fr[n]; l++) { 117 int ans = 0; 118 for(int r = l; r <= fr[n]; r++) { 119 for(int k = le[r]; k <= re[r]; k++) { 120 if(bin[a[k]]) { 121 bin[a[k]] & 1 ? ans++ : ans--; 122 } 123 bin[a[k]]++; 124 } 125 sum[l][r] = ans; 126 } 127 for(int k = le[l]; k <= n; k++) { 128 bin[a[k]]--; 129 } 130 } 131 132 int lastans = 0; 133 for(int i = 1, x, y; i <= m; i++) { 134 read(x); 135 read(y); 136 x = (x + lastans) % n + 1; 137 y = (y + lastans) % n + 1; 138 if(x > y) { 139 std::swap(x, y); 140 } 141 lastans = ask(x, y); 142 printf("%d ", lastans); 143 } 144 145 return 0; 146 }
udpate：其实可以删去只出现一次的数。不过恶意卡的话没啥优化效果。