数颜色（不用莫队，可区间修改）

注意到修改操作很少，那么以修改操作为划分点，我们得到若干个只有询问的区间。对于这些区间，直接做静态区间元素种类计数（就是按右端点排序然后树状数组的那个解法），做完一个区间后暴力执行修改。

记询问次数是$Q$,修改操作是$M$,则复杂度上界为$\mathcal O(NM+Q(\log n+\log Q))$.

拓展：

区间修改：反正我们的修改都是暴力修改，区间修改不会增大复杂度

此外，还可以通过根号重构做到大约$O((M+Q)\sqrt{(M+Q})$,但似乎不好写。

#define MAXN 20011
int fx[MAXN], diff;
int n,m;
int place(int val){return std::lower_bound(fx+1,fx+diff+1,val)-fx;}
struct BIT
{
    int t[MAXN];
    #define lowb (i&-i)
    void modify(int i,int k)
    {
        while(i<=n)t[i]+=k,i+=lowb;
    }
    int Qsum(int i)
    {
        int res=0;
        while(i)res+=t[i],i-=lowb;
        return res;
    }
}t;
struct one
{
    int type,x,y,dex;
    bool operator <(const one& you)const{return y<you.y;}
}q[MAXN];
int a[MAXN],last[MAXN],ans[MAXN];
int Get(){char c=getchar();while(c<'A'||c>'Z')c=getchar();return c=='Q'?1:0;}
int main()
{
     n=read(),m=read();
    for(int i=1;i<=n;++i)fx[++diff]=a[i]=read();
    for(int i=1;i<=m;++i)
    {
        q[i].type=Get(),q[i].x=read(),q[i].y=read(),q[i].dex=i;
        if(!q[i].type)fx[++diff]=q[i].y;
    }
    std::sort(fx+1,fx+diff+1),diff=std::unique(fx+1,fx+diff+1)-fx-1;
    for(int i=1;i<=n;++i)a[i]=place(a[i]);
    for(int i=1,j;i<=m;i=j)
    {
        j=i;
        while(j<=m&&q[j].type)++j;
        std::sort(q+i,q+j);
        int all=0;
        for(int x=1;x<=n;++x)
        {
            if(last[a[x]])t.modify(last[a[x]],-1),--all;
            t.modify(last[a[x]]=x,1),++all;
            while(i<j&&q[i].y==x){ans[q[i].dex]=all-t.Qsum(q[i].x-1);++i;}
        }
        for(int x=1;x<=diff;++x)
            if(last[x])t.modify(last[x],-1),last[x]=0;
        while(j<=m&&!q[j].type)a[q[j].x]=place(q[j].y),++j;
    }
    for(int i=1;i<=m;++i)
        if(q[i].type)printf("%d\n",ans[i]);
    return 0;
}