#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=3e5+25;
int a[N],n,m,b[N],qcnt,rcnt;
int cnt[N];
struct Query{
    int id,l,r,tim,val;
}q[N];
struct Change{
    int k,pos;
}modify[N];
int pos[N],ans[N];
map<int,int>mp;
inline bool cmp(Query x,Query y){
    if(pos[x.l]!=pos[y.l])return x.l<y.l;
    if(pos[x.r]!=pos[y.r])return x.r<y.r;
    return x.id<y.id;
}
inline void add(int x){++cnt[x];}
inline void del(int x){--cnt[x];}
inline void init(){
    int tot=0;
    cin>>n>>m;
    for(int i=1;i<=n;++i){
	    cin>>a[i];
	    if(!mp[a[i]])mp[a[i]]=++tot;
	    a[i]=mp[a[i]];
    }
    char c;
    int x,y,z;
    for(int i=1;i<=m;i++){
        cin>>c;
        if(c=='C'){
            ++rcnt;
            cin>>x>>y;
            modify[rcnt].pos=x;
            modify[rcnt].k=mp[y];
        }else{
            ++qcnt;
            cin>>x>>y>>z;
            q[qcnt]=(Query){qcnt,x,y,rcnt,mp[z]};
        }
    }
    int block=pow(n,2.0/3.0);
    for(int i=1;i<=n;i++)
        pos[i]=i/block;
    sort(q+1,q+1+qcnt,cmp);
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    init();
    int l=1,r=0,last=0;
    for(int i=1;i<=m;i++){
        while(l>q[i].l)--l,add(a[l]);
        while(r<q[i].r)++r,add(a[r]);
        while(l<q[i].l)del(a[l]),++l;
        while(r>q[i].r)del(a[r]),--r;
        while(last<q[i].tim){
            last++;
            if(modify[last].pos>=l&&modify[last].pos<=r){
                del(a[modify[last].pos]);
                add(modify[last].k);
            }
            swap(a[modify[last].pos],modify[last].k);
        }
        while(last>q[i].tim){
            if(modify[last].pos>=l&&modify[last].pos<=r){
                del(a[modify[last].pos]);
                add(modify[last].k);
            }
            swap(a[modify[last].pos],modify[last].k);
            last--;         
        }
        ans[q[i].id]=cnt[q[i].val];
    }
    for(int i=1;i<=qcnt;i++)
        cout<<ans[i]<<'\n';
    return 0;
}