#include<bits/stdc++.h>
#define N 100005
using namespace std;
int n,len,m,a[N],tot,tot1,ans[N];
unordered_map<int,int>cnt;
struct Q{int l,r,k,pos,lst;}q[N],q1[N];
bool cmp(Q x,Q y){
    if(x.l/len!=y.l/len)return x.l/len<y.l/len;
    else if(x.r/len!=x.r/len)return x.r/len<y.r/len;
    else return x.lst<y.lst;
}
void add(int x){
    cnt[x]++;
}
void remove(int x){
    cnt[x]--;
}
void update(int t,int x){
    if(q1[t].l>=q[x].l&&q1[t].l<=q[x].r){
        add(q1[t].r);
        remove(a[q1[t].l]);
    }
    swap(q1[t].r,a[q1[t].l]); 
}
int main(){
    scanf("%d%d",&n,&m);
    len=pow(n,0.2/0.3)+1;
    for(int i=1;i<=n;i++)
        scanf("%d",a+i);
    for(int i=1;i<=m;i++){
        char s[5];
        int aa,b,k;
        scanf("%s%d%d",s,&aa,&b);
        if(s[0]=='C')q1[++tot1].l=aa,q1[tot1].r=b;
        else scanf("%d",&k),q[++tot].l=aa,q[tot].r=b,q[tot].lst=tot1,q[tot].pos=tot,q[tot].k=k;
    }
    sort(q+1,q+tot+1,cmp);
    int l=1,r=0,t=0;
    for(int i=1;i<=tot;i++){
        while(l<q[i].l)remove(a[l++]);
        while(r<q[i].r)add(a[++r]);
        while(l>q[i].l)add(a[--l]);
        while(r>q[i].r)remove(a[r--]);
        while(t>q[i].lst)update(t--,i);
        while(t<q[i].lst)update(++t,i);
        ans[q[i].pos]=cnt[q[i].k];
    }
    for(int i=1;i<=tot;i++) 
        printf("%d\n",ans[i]);
}