【luogu P1903 [国家集训队]数颜色】 题解

题目链接：https://www.luogu.org/problemnew/show/P1903

裸的。。。带修莫队。。。

比较麻烦吧（对我来说是的）

两个变量分开记录查询和修改操作。

 #include <iostream>

 #include <cstdio>

 #include <algorithm>

 #include <cmath>

 #define ri register

 using namespace std;

 const int maxn = ;

 int n, m, bl, answer = , qnum = , unum = , curR, curL, now;

 int ans[maxn],a[maxn],cnt[maxn];

 struct query{

     int l, r, p, t;

     bool operator < (const query &x) const {

     if(l / bl != x.l / bl) return l / bl < x.l / bl;

     if(r / bl != x.r / bl) return r / bl < x.r / bl;

     return t < x.t;

   }

 }q[maxn];

 struct update{

     int pos, val;

 }u[maxn];

 inline void add(int pos) {

   if(++ cnt[pos] == ) answer ++;

 }

 inline void remove(int pos) {

   if(-- cnt[pos] == ) answer --;

 }

 inline void change(int now, int i) {

   if(q[i].l <= u[now].pos && u[now].pos <= q[i].r) {

     if( --cnt[a[u[now].pos]] ==  ) answer--;

     if( ++cnt[u[now].val] == )      answer++;

   }

   swap(a[u[now].pos], u[now].val);

 }

 int main()

 {

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

     bl = pow(n,1.0/);

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

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

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

     {

     int ch, x, y;

     while((ch = getchar()) != 'Q' && ch != 'R');

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

     if(ch == 'Q') {

       q[++ qnum].l = x;

       q[qnum].r = y;

       q[qnum].t = unum;

       q[qnum].p = qnum;

     } else {

       u[++unum].pos = x;

       u[unum].val = y;

     }

   }

     sort(q+,q+qnum+);

     curL = q[].l, curR = curL - , now = ;

   for(ri int i = ; i <= qnum; i ++) {

     while(curL < q[i].l) remove(a[curL ++]);

     while(curL > q[i].l) add(a[-- curL]);

     while(curR < q[i].r) add(a[++ curR]);

     while(curR > q[i].r) remove(a[curR --]);

     while(now < q[i].t) change(++ now, i);

     while(now > q[i].t) change(now --, i);

     ans[q[i].p] = answer;

   }

     for(ri int i = ; i <= qnum; i++)

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

     return ;

 }