恩。。什么树状数组套主席树？大概是可以修改并且支持前缀减法的数据结构吧。。。
咦。可以离线？上莫队不就行了，干嘛要数据结构。。。
哦还要修改，那就三维莫队就好了，happy ending！
1 /************************************************************** 2 Problem: 2120 3 User: rausen 4 Language: C++ 5 Result: Accepted 6 Time:488 ms 7 Memory:5540 kb 8 ****************************************************************/ 9 10 #include <cstdio> 11 #include <cmath> 12 #include <algorithm> 13 14 using namespace std; 15 const int N = 1e4 + 5; 16 const int cnt_C = 1e6 + 5; 17 const int Maxlen = N * 35; 18 19 int n, m, sz, cnt_b; 20 int w[N], c[N], pre[N]; 21 int now; 22 int cnt_c, cnt_q; 23 int ans[N], vis[N], cnt[cnt_C]; 24 char buf[Maxlen], *ch = buf; 25 int Len; 26 27 struct oper_change { 28 int x, y, pre; 29 oper_change() {} 30 oper_change(int _x, int _y, int _p) : x(_x), y(_y), pre(_p) {} 31 } oc[N]; 32 33 struct oper_query { 34 int x, y, id, t; 35 oper_query() {} 36 oper_query(int _x, int _y, int _i, int _t) : x(_x), y(_y), id(_i), t(_t) {} 37 38 inline bool operator < (const oper_query &X) const { 39 return w[x] == w[X.x] ? w[y] == w[X.y] ? t < X.t : w[y] < w[X.y] : w[x] < w[X.x]; 40 } 41 } oq[N]; 42 43 inline int read() { 44 int x = 0; 45 while (*ch < '0' || '9' < *ch) ++ch; 46 while ('0' <= *ch && *ch <= '9') 47 x = x * 10 + *ch - '0', ++ch; 48 return x; 49 } 50 51 inline void reverse(int p) { 52 if (vis[p]) { 53 if ((--cnt[c[p]]) == 0) --now; 54 } else { 55 if ((++cnt[c[p]]) == 1) ++now; 56 } 57 vis[p] ^= 1; 58 } 59 60 inline int update(int p, int C) { 61 if (vis[p]) { 62 reverse(p); 63 c[p] = C; 64 reverse(p); 65 } else c[p] = C; 66 } 67 68 int main() { 69 Len = fread(ch, 1, Maxlen, stdin); 70 buf[Len] = ' '; 71 int i, j, l, r, x, y; 72 char op; 73 n = read(), m = read(); 74 sz = (int) pow(n, 2.0 / 3); 75 if (!sz) sz = 1; 76 for (i = 1; i <= n; ++i) { 77 c[i] = pre[i] = read(); 78 if (i % sz == 1 || sz == 1) ++cnt_b; 79 w[i] = cnt_b; 80 } 81 for (i = 1; i <= m; ++i) { 82 while (*ch != 'Q' && *ch != 'R') ++ch; 83 op = *ch; 84 x = read(), y = read(); 85 if (op == 'R') 86 oc[++cnt_c] = oper_change(x, y, pre[x]), pre[x] = y; 87 else { 88 if (x > y) swap(x, y); 89 oq[++cnt_q] = oper_query(x, y, cnt_q, cnt_c); 90 } 91 } 92 sort(oq + 1, oq + cnt_q + 1); 93 for (i = l = 1, r = oq[0].t = 0; i <= cnt_q; ++i) { 94 for (j = oq[i - 1].t + 1; j <= oq[i].t; ++j) update(oc[j].x, oc[j].y); 95 for (j = oq[i - 1].t; j > oq[i].t; --j) update(oc[j].x, oc[j].pre); 96 while (r < oq[i].y) reverse(++r); 97 while (r > oq[i].y) reverse(r--); 98 while (l > oq[i].x) reverse(--l); 99 while (l < oq[i].x) reverse(l++); 100 ans[oq[i].id] = now; 101 } 102 for (i = 1; i <= cnt_q; ++i) 103 printf("%d ", ans[i]); 104 return 0; 105 }