本地可过样例。

#include<bits/stdc++.h>
using namespace std;
constexpr int MAXN=133333+10,MAXM=133333+10;
int n,m,a[MAXN],tmp[MAXN],cntc,cntq,ans[MAXM],T,l,r,cnt[MAXN],tans,chn;
struct change{
    int p,l,c;
}c[MAXM];
struct query{
    int id,l,r,c;
}q[MAXM];
template<typename T>
T read(){
    T f=1,x=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+(ch^48);ch=getchar();}
    return f*x;
}
namespace sol{
    bool cmp(query x,query y){
        int lx=(x.l-1)/T,ly=(y.l-1)/T;
        if(lx!=ly)return lx<ly;
        else{
            int rx=(x.r-1)/T,ry=(y.r-1)/T;
            if(rx!=ry){
                if(lx&1)return rx>ry;
                else return rx<ry;
            }else{
                int cx=(x.c-1)/T,cy=(y.c-1)/T;
                if(rx&1)return cx>cy;
                else return cx<cy;
            }
        }
    }
    void add(int p){
        ++cnt[a[p]];
        if(cnt[a[p]]==1)++tans;
    }
    void del(int p){
        --cnt[a[p]];
        if(cnt[a[p]]==0)--tans;
    }
    void chg(int p,int x){
        if(l<=p&&p<=r)del(p);
        a[p]=x;
        if(l<=p&&p<=r)add(p);
    }
    void solve(){
        n=read<int>();m=read<int>();
        for(int i=1;i<=n;++i){
            tmp[i]=a[i]=read<int>();
        }
        while(m--){
            char op[10];
            scanf("%s",op);
            if(op[0]=='Q'){
                int l1=read<int>(),r1=read<int>();
                ++cntq;
                q[cntq]={cntq,l1,r1,cntc};
            }else{
                int p1=read<int>(),c1=read<int>();
                c[++cntc]={p1,tmp[p1],c1};
                tmp[p1]=c1;
            }
        }
        T=pow(n,2.0/3.0);
        sort(q+1,q+cntq+1,cmp);
        l=r=1;add(1);
        for(int i=1;i<=cntq;++i){
            while(l>q[i].l)add(--l);
            while(r<q[i].r)add(++r);
            while(l<q[i].l)del(l++);
            while(r>q[i].r)del(r--);
            while(chn<q[i].c){
                ++chn;
                chg(c[chn].p,c[chn].c);
            }
            while(chn>q[i].c){
                chg(c[chn].p,c[chn].l);
                --chn;
            }
            ans[q[i].id]=tans;
            // printf("q[%d]={%d,%d,%d,%d}\n",i,q[i].id,q[i].l,q[i].r,q[i].c);
        }
        for(int i=1;i<=cntq;++i)printf("%d\n",ans[i]);
    }
}
int main(){
    sol::solve();
    return 0;
}