BZOJ2120数颜色【带修改莫队】

  1 #include 
  2 #define INF 0x3f3f3f3f
  3 #define LL long long
  4 using namespace std;
  5 const int MAXN = 1e4+10;
  6 const int MAXM = 1e6+10;
  7 int N, M;
  8 int h[MAXN], num[MAXN];
  9 int ans[MAXN], sum[MAXM];
 10 struct Query
 11 {
 12     int l, r, id, t;
 13 }Q[MAXN];
 14 
 15 struct Time
 16 {
 17     int ip, co, lt;
 18 }t[MAXN];
 19 int last[MAXN];
 20 
 21 bool cmp(Query a, Query b)
 22 {
 23     if(h[a.l] != h[b.l]) return h[a.l] < h[b.l];
 24     else{
 25         if(h[a.r] != h[b.r]) return h[a.r] < h[b.r];
 26         else return a.t < b.t;
 27     }
 28 }
 29 
 30 int update(int tt, int L, int R, int no)
 31 {
 32     int res = 0;
 33     int x = t[tt].ip, val = t[tt].co, lst = t[tt].lt;
 34     if(t[tt].ip >= L && t[tt].ip <= R){
 35         if(sum[num[x]] == 1) res--;
 36         sum[num[x]]--;
 37         if(no == 1){
 38             if(sum[val] == 0) res++;
 39             sum[val]++;
 40         }
 41         else if(no == -1){
 42             if(sum[lst] == 0) res++;
 43             sum[lst]++;
 44         }
 45     }
 46     if(no == 1) num[x] = val;
 47     else if(no == -1) num[x] = lst;
 48     return res;
 49 }
 50 
 51 int add(int x, int val)
 52 {
 53     int res = 0;
 54     if(val == 1 && sum[num[x]] == 0) res++;
 55     if(val == -1 && sum[num[x]] == 1) res--;
 56     sum[num[x]]+=val;
 57     return res;
 58 }
 59 
 60 int main()
 61 {
 62     scanf("%d %d", &N, &M);
 63     for(int i = 1; i <= N; i++){
 64         scanf("%d", &num[i]);
 65         last[i] = num[i];
 66     }
 67     int lim = pow(N, (double)2/3);
 68     for(int i = 1; i <= N; i++) h[i] = (i-1)/lim+1;
 69     int cnt = 0, Tcnt = 0;
 70     char com[5];
 71     for(int i = 1; i <= M; i++){
 72         scanf("%s", com);
 73         if(com[0] == 'Q'){
 74             cnt++;
 75             scanf("%d %d", &Q[cnt].l, &Q[cnt].r);
 76             Q[cnt].t = Tcnt;
 77             Q[cnt].id = cnt;
 78         }
 79         else{
 80             Tcnt++;
 81             scanf("%d %d", &t[Tcnt].ip, &t[Tcnt].co);
 82             t[Tcnt].lt = last[t[Tcnt].ip];
 83             last[t[Tcnt].ip] = t[Tcnt].co;
 84             //printf("%d %d\n", t[Tcnt].co, t[Tcnt].lt);
 85         }
 86     }
 87     sort(Q+1, Q+1+cnt, cmp);
 88 
 89     int L = 1, R = 0, T = 0, cur = 0;
 90     for(int i = 1; i <= cnt; i++){
 91         while(T 1);
 92         while(T > Q[i].t) cur+=update(T--, L, R, -1);
 93         while(L 1);
 94         while(L > Q[i].l) cur+=add(--L, 1);
 95         while(R 1);
 96         while(R > Q[i].r) cur+=add(R--, -1);
 97         ans[Q[i].id] = cur;
 98     }
 99 
100     for(int i = 1; i <= cnt; i++){
101         printf("%d\n", ans[i]);
102     }
103 
104     return 0;
105 
106 }