数颜色

分块题
纪念自己写错一个小地方WA了半天
  1 #include <cstdio>
  2 #include <cstring>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <set>
  6 #include <map>
  7 using namespace std;
  8 typedef long long LL;
  9 
 10 const int maxs = 100;
 11 const int maxb = 110;
 12 const int maxn = 1e4 + 10;
 13 
 14 int n, m;
 15 
 16 int A[maxn], pre[maxn], nxt[maxn], B[maxn];
 17 char str[10];
 18 bool lazy[maxb];
 19 int last[1000010];
 20 int x, y;
 21 
 22 int ans;
 23 
 24 int belong(int xx) {
 25     return (xx + maxs - 1) / maxs;
 26 }
 27 
 28 void re(int xx) {
 29     lazy[xx] = 0;
 30     for (int i = (xx - 1) * maxs + 1; i <= xx * maxs && i <= n; i++) {
 31         B[i] = pre[i];
 32     }
 33     sort(B + (xx - 1) * maxs + 1, B + min(n + 1, xx * maxs + 1));
 34 }
 35 
 36 void init() {
 37     for (int i = 1; i <= n; i++) {
 38         pre[i] = last[A[i]];
 39         last[A[i]] = i;
 40         if (pre[i]) nxt[pre[i]] = i;
 41     }
 42     for (int i = 1; i <= belong(n); i++) {
 43         lazy[i] = 1;
 44     }
 45 }
 46 
 47 
 48 void update() {
 49     if (A[x] == y) return;
 50     A[x] = y;
 51     lazy[belong(x)] = 1;
 52     if (nxt[x]) pre[nxt[x]] = pre[x], lazy[belong(nxt[x])] = 1;
 53     if (pre[x]) nxt[pre[x]] = nxt[x], lazy[belong(pre[x])] = 1;
 54     int _p= 0, _n = 0;
 55     for (int i = 1; i <= n; i++) {
 56         if (i < x && A[i] == y) _p = i;
 57         if (i > x && A[i] == y) {
 58             _n = i;
 59             break;
 60         }
 61     }
 62     pre[x] = _p;
 63     nxt[x] = _n;
 64     if (_p) nxt[_p] = x, lazy[belong(_p)] = 1;
 65     if (_n) pre[_n] = x, lazy[belong(_n)] = 1;
 66 }
 67 
 68 void query() {
 69     ans = 0;
 70     int _x = x, _y = y;
 71     while (_x <= _y && _x % maxs != 1) if (pre[_x++] < x) ans++;
 72     while (_x <= _y && _y % maxs != 0) if (pre[_y--] < x) ans++;
 73     while (_x <= _y) {
 74         int tmp = belong(_x);
 75         if (lazy[tmp]) re(tmp);
 76         int cnt = lower_bound(B + (tmp - 1) * maxs + 1, B + min(n + 1, tmp * maxs + 1), x) 
 77                             -(B + (tmp - 1) * maxs + 1) ;
 78         ans += cnt;
 79         _x += maxs;
 80     }
 81     printf("%d
", ans);
 82 }    
 83 
 84 int main() {
 85     scanf("%d%d", &n, &m);
 86     for (int i = 1; i <= n; i++) {
 87         scanf("%d", &A[i]);
 88     }
 89     getchar();
 90     init();
 91     while (m--) {
 92         scanf("%s", str);
 93         scanf("%d%d", &x, &y);
 94         if (str[0] == 'Q') {
 95             query();
 96         } else {        
 97             update();
 98         }
 99     }
100     return 0;
101 }