///P1903 [国家集训队] 数颜色 / 维护队列 带修改莫队算法模板：求区间不同数的个数+单点修改
#include<bits/stdc++.h>
using namespace std;
const int maxn=1000005;
typedef long long ll;
int n,m,sz,cnt[maxn],a[maxn],Ans,ans[maxn];
struct Change
{
    int p,col;
} c[maxn];
struct Query
{
    int l,r,t,id;
    bool operator<(Query& b)
    {
        return l/sz==b.l/sz?(r/sz==b.r/sz?t<b.t:r<b.r):l<b.l;//同一块内按修改时间排序
    }
} q[maxn];
void add(int x)
{
    cnt[x]++;
    if (cnt[x]==1)
        ++Ans;
}
void del(int x)
{
    cnt[x]--;
    if (cnt[x]==0)
        --Ans;
}
/*这个函数会执行或回退修改ti（执行还是回退取决于是否执行过，具体通过swap实现），
x表明当前的询问是第x次询问，如果第ti次修改碰巧修改了区间[q[x].l,q[x].r]便要更新答案
*/
void modify(int x,int ti)
{
    if(c[ti].p>=q[x].l&&c[ti].p<=q[x].r)
    {
        del(a[c[ti].p]);//去掉这个位置原来的颜色
        add(c[ti].col);//改成现在的新颜色
    }
    swap(a[c[ti].p],c[ti].col);//这一步操作为后面的回退做准备的
}
int main()
{
    while(scanf("%d%d",&n,&m)!=-1)
    {
        memset(cnt,0,sizeof(cnt));
        sz=pow(n,0.66666);//准备对n分块操作
        for (int i=1; i<=n; i++)
            scanf("%d",&a[i]);
        char op[10];
        int ccnt=0,qcnt=0;
        for (int i=1; i<=m; ++i)
        {
            scanf("%s",op);
            if (op[0]=='Q')
            {
                ++qcnt;//记录进行了多少次查询
                scanf("%d%d",&q[qcnt].l,&q[qcnt].r) ;
                q[qcnt].t=ccnt;//记录在此之前进行了多少次修改 ccnt这个值是在修改时才累加
                q[qcnt].id=qcnt;
            }
            else
            {
                ++ccnt;
                scanf("%d%d",&c[ccnt].p,&c[ccnt].col);
            }
        }
        sort(q+1,q+qcnt+1);//莫队基本操作，分块加排序（注意此处的排序增加了一维时间）
        int l=1,r=0,now=0;
        Ans=0;
        for (int i=1; i<=qcnt; ++i)  //针对每一次查询的处理
        {
            //下面4个while循环是首先当做没有修改操作，按照通常的莫队来处理
            while (r<q[i].r)
                add(a[++r]);
            while(l>q[i].l)
                add(a[--l]);
            while (l<q[i].l)
                del(a[l++]);
            while (r>q[i].r)
                del(a[r--]);
            //接下来开始处理修改操作，在第i次查询前总共进行了t次修改
            while (now<q[i].t)
                modify(i,++now);
            while (now>q[i].t)
                modify(i,now--);
            ans[q[i].id]=Ans;
        }
        for (int i=1; i<=qcnt; ++i)
            printf("%d\n",ans[i]);
    }
    return 0;
}

代码理解：

while (now<q[i].t) //在第i次查询前有修改，那么要把那些修改的行为加上去 修改了多少次就要循环多少次
{
modify(i,++now);
}
while (now>q[i].t) // 因为q数组是排过序的，所以可能出现某次查询其实没有修改那么多，但是因为前面的查询把一些地方修改了，所以这里需要还原
{
modify(i,now--);
}

关于第\(2\)个\(while\)可以看下面的例子：
例如有\(3\)次查询和\(2\)次修改如下时间关系：
\(Q1\) \(Q2\) \(R1\) \(R2\) \(Q3\)
我们假设\(R1\) \(R2\)这两次修改都涉及到了\(Q2\)和\(Q3\)区间中的某个数
但是查询\(Q2\)时还没有进行修改。
那么如果对查询排序后的结果得到的顺序是\(Q1 Q3 Q2\)
那么因为\(Q3\)之前经过了\(2\)次修改，所以在查询\(Q3\)时，我们要做两次修改，
那么后面在执行\(Q2\)时需要把这两次修改回退回去。

void modify(int x,int ti) {
if (c[ti].p>=q[x].l&&c[ti].p<=q[x].r) {
del(a[c[ti].p]);//去掉这个位置原来的颜色
add(c[ti].col);//改成现在的新颜色
}
swap(a[c[ti].p],c[ti].col);//这一步操作为后面的回退做准备的
}

\(c[ti].p\)表示第\(t_i\)次修改的位置