RT

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
#include<map>
#include<queue>
#include<stack>
#define INF 0x3f3f3f3f
#define int long long
#define mod 998244353
#define MAXN 1000001
using namespace std;
int n,m,b;
int a[MAXN],p[MAXN],ans;//值的出现次数
int u,j,o[MAXN];//询问的答案
pair<int,int> c[MAXN];//first修改的位置,second修改的值
int idb(int x){
    return x/b;
}
struct  kx{
    int l,r,id,t;//这个询问值的修改次数，id为查询次数
    bool operator <(const kx &tmp) const{
        if(idb(l)==idb(tmp.l)){
            if(idb(r)==idb(tmp.r)) return t<tmp.t;
            return r<tmp.r;
        }
        return l<tmp.l;
    }
};
kx k[MAXN];
bool cmp(kx x,kx y){
    return x<y;
}
void add(int x){
    p[x]++;
    if(p[x]==1) ans++;
}
void del(int x){
    p[x]--;
    if(p[x]==0) ans--;
}
signed main(){
    ios::sync_with_stdio(false); 
    cin>>n>>m;
    double g=pow(n,(double)2/3);
    b=g;
    cout<<b;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=m;i++){
        char t;
        cin>>t;
        if(t=='Q'){
            u++;
            cin>>k[u].l>>k[u].r;
            k[u].id=u;
            k[u].t=j;
        }else{
            int x,y;
            cin>>x>>y;
            j++;
            c[j]=make_pair(x,y);
        }
    }
    sort(k+1,k+1+u,cmp);
    int sl=1,sr=0,st=0;
    for(int i=1;i<=u;i++){
        while(sl>k[i].l) add(a[--sl]);
        while(sr<k[i].r) add(a[++sr]);
        while(sl<k[i].l) del(a[sl++]);
        while(sr>k[i].r) del(a[sr--]);
        while(st<k[i].t){
            int tmp=a[c[++st].first];
            a[c[st].first]=c[st].second;
            if(c[st].first>=k[i].l&&c[st].first<=k[i].r) add(a[c[st].first]);
            c[st].second=tmp;
            if(c[st].first>=k[i].l&&c[st].first<=k[i].r) del(c[st].second);
        }
        while(st>k[i].t){
            int tmp=a[c[st].first];
            a[c[st].first]=c[st].second;
            if(c[st].first>=k[i].l&&c[st].first<=k[i].r) add(a[c[st].first]);
            c[st].second=tmp;
            if(c[st].first>=k[i].l&&c[st].first<=k[i].r) del(c[st].second);
            st--;
        }
        o[k[i].id]=ans;
    }
    for(int i=1;i<=u;i++){
        cout<<o[i]<<"\n";
    }
    return 0;
}