#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5;

int n,m,c[N],len,ans[N],f[N],cnta,cntu,d[N],cnt,L,R,last;

struct node{
	int id,t,l,r,k;
	friend bool operator<(node a,node b){
		if(a.l/len!=b.l/len) return a.l>b.l;
		if(a.r/len!=b.r/len) return a.r>b.r ;
		return a.t>b.t;
	}
}a[N];

struct Node{
	int p,x;
}u[N];

void add(int x){
	f[x]++;
}

void del(int x){
	f[x]--;
}

void update(int x){
	if(u[x].p>=L && u[x].p<=R){
		add(u[x].x);
		del(c[u[x].p]);
	}
	swap(c[u[x].p],u[x].x);
}

signed main(){
	cin>>n>>m;
	len=pow(n,2.0/3.0);
	for(int i=1;i<=n;i++){
		cin>>c[i];
		d[++cnt]=c[i];
	} 
	for(int i=1;i<=m;i++){
		int y,z,t;
		char op;
		cin>>op>>y>>z;
		if(op=='Q'){
			cin>>t;
			cnta++;
			a[cnta]={cnta,cntu,y,z,t};
			d[++cnt]=t;
		}else{
			u[++cntu]={y,z};
			d[++cnt]=z;
		}
	} 
	sort(d+1,d+cnt+1);
	cnt=unique(d+1,d+cnt+1)-d;
	for(int i=1;i<=n;i++) c[i]=lower_bound(d+1,d+cnt+1,c[i])-d;
	for(int i=1;i<=cntu;i++) u[i].p=lower_bound(d+1,d+cnt+1,u[i].p)-d;
	for(int i=1;i<=cnta;i++) a[i].k=lower_bound(d+1,d+cnt+1,a[i].k)-d;
	sort(a+1,a+cnta+1);
	L=1,R=0,last=0;
	for(int i=1;i<=cnta;i++){
		while(L>a[i].l) add(c[--L]);
		while(R<a[i].r) add(c[++R]);
		while(L<a[i].l) del(c[L++]);
		while(R>a[i].r) del(c[R--]);
		while(last<a[i].t) update(++last);
		while(last>a[i].t) update(last--);
		ans[a[i].id]=f[a[i].k];
	} 
	for(int i=1;i<=cnta;i++){
		cout<<ans[i]<<endl;
	}
	
	return 0;
}