Dynamic len(set(a[L:R])) UVA - 12345（这么过分一定要写博客）

给出一个有n个元素的数组，有以下两种操作：Q x y，求出区间[x,y)内不同元素的个数，

M x y，把第x个元素的值修改为y。注意题目中的下标是从0开始的

这题超级超级坑

妈的一个水题找了几个小时的BUG

  这样AC

这样WA

 吃一堑长一智  妈的毒瘤啊 

 

 #include <bits/stdc++.h>

 using namespace std;

 typedef long long LL;

 const int maxn = 1e6 + ;

 int n, m, L, R, ans, sz, qsz, tsz;

 int a[maxn], ANS[maxn], num[maxn], now[maxn], flag[maxn];

 struct node {

     int l, r, id, t;

     node() {}

     node(int l, int r, int id, int t): l(l), r(r), id(id), t(t) {}

     bool operator < (const node &b)const {

         if (l / sz == b.l / sz) {

             if (r / sz == b.r / sz) return t < b.t;

             return r < b.r;

         }

         return l < b.l;

     }

 } qu[maxn];

 struct node1 {

     int pos, x, y;

     node1() {}

     node1(int pos, int x, int y): pos(pos), x(x), y(y) {}

 } c[maxn];

 void add(int val) {

     if (num[a[val]] == ) ans++;

     num[a[val]]++;

 }

 void del(int val)  {

     num[a[val]]--;

     if (num[a[val]] == ) ans--;

 }

 void change(int pos, int x) {

     if (L <= pos && pos <= R) del(pos);

     a[pos] = x;

     if (L <= pos && pos <= R) add(pos);

 }

 int main() {

     scanf("%d%d", &n, &m);

     sz = (int)sqrt((double)n + 0.5);

     qsz = tsz = ;

     for (int i =  ; i <= n ; i++) {

         scanf("%d", &a[i]);

         now[i] = a[i];

     }

     for (int i =  ; i <= m ; i++) {

         char s[];

         scanf("%s", s);

         if(s[] == 'Q') {

             int l, r;

             scanf("%d%d", &l, &r);

             l++;

             qsz++;

             qu[qsz] = node(l, r, qsz, tsz);

         } else {

             int pos, x;

             scanf("%d%d", &pos, &x);

             pos++;

             tsz++;

             c[tsz].pos = pos, c[tsz].x = x, c[tsz].y = now[pos];

             now[pos] = x;

         }

     }

     for (int i =  ; i <= n ; i++) now[i] = a[i];

     int t = ;

     sort(qu + , qu +  + qsz);

     L = , R = , ans = ;

     for (int i =  ; i <= qsz ; i++) {

         while(L < qu[i].l) del(L++);

         while(R > qu[i].r) del(R--);

         while(L > qu[i].l) add(--L);

         while(R < qu[i].r) add(++R);

         while(t < qu[i].t) t++, change(c[t].pos, c[t].x);

         while(t > qu[i].t) change(c[t].pos, c[t].y), t--;

         ANS[qu[i].id] = ans;

     }

     for (int i =  ; i <= qsz ; i++)

         printf("%d\n", ANS[i]);

     return ;

 }