#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
int n,m,l,r,x,k,tmp,tim,b,cnt,_cnt,idx,cidx;
int f[N],g[N],s[N],ans[N],bl[N];
unordered_map<int,int>cast;
char op;
struct upnode{
	int k,x;
}up[N];
struct node{
	int l,r,k,tim,id;
	bool operator<(const node&nd)const{
		if(bl[l]!=bl[nd.l])return l<nd.l;
		if(bl[r]!=bl[nd.r])return r<nd.r;
		return tim<nd.tim;
	}
}Q[N];
inline void add(int x){
	s[x]++;
}
inline void del(int x){
	s[x]--;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin>>n>>m;
	b = pow(n,3/4.0);
	for(int i = 1;i<=n;i++){
		bl[i] = i/b;
	}
	for(int i = 1;i<=n;i++){
		cin>>f[i];
		g[++cnt]=f[i];
	}
	for(int i = 1;i<=m;i++){
		cin>>op>>l>>r;
		if(op=='C'){
			up[++tim]={l,r};
			g[++cnt] = r;
		}else if(op=='Q'){
			cin>>k;
			Q[++idx] = {l,r,k,tim,idx};
			g[++cnt]=k;
		}
	}
	sort(g+1,g+1+cnt);
	for(int i = 1;i<=cnt;i++){
		if(cast.find(g[i])==cast.end()){
			cast[g[i]]=++_cnt;
		}
	}
	for(int i = 1;i<=n;i++)f[i]=cast[f[i]];
	for(int i = 1;i<=tim;i++)up[i].x = cast[up[i].x];
	for(int i = 1;i<=idx;i++)Q[i].k = cast[Q[i].k];
	
	sort(Q+1,Q+1+idx);
	for(int i = 1,l=1,r=0,t=0;i<=idx;i++){
		while(t<Q[i].tim){
			++t;
			int p = up[t].k;
			if(l<=p&&p<=r){
				del(f[p]);
				add(up[t].x);
			}
			swap(f[p],up[t].x);
		}
		while(t>Q[i].tim){
			int p = up[t].k;
			if(l<=p&&p<=r){
				del(f[p]);
				add(up[t].x);
			}
			swap(f[p],up[t].x);
			t--;
		}		
		while(l<Q[i].l)del(f[l++]);
		while(r>Q[i].r)del(f[r--]);
		while(l>Q[i].l)add(f[--l]);
		while(r<Q[i].r)add(f[++r]);
		ans[Q[i].id]=s[Q[i].k];
	}
	for(int i = 1;i<=idx;i++){
		cout<<ans[i]<<"\n";
	}
}