#include "bits/stdc++.h"
using namespace std;
const int N=2000005;
int n,m,c[N],al,bl,ans[N],cnt[N],sz,d[N],tot,L=1,R=0,now=0;
char opt[5];
struct node{int l,r,k,t,id;}a[N];
struct nd{int p,col;}b[N];
bool cmp(node x,node y){
	if(x.l/sz==y.l/sz){
		if(x.r/sz==y.r/sz)return x.t<y.t;
		return (x.l/sz)&1?x.r<y.r:x.r>y.r;
	}
	return x.l/sz<y.l/sz;
}
inline void add(int x){cnt[x]++;}
inline void del(int x){cnt[x]--;}
inline void update(int x,int t){
	if(L<=b[t].p&&b[t].p<=R){
		add(c[b[t].p]);
		del(b[t].col);
	}
	swap(c[b[t].p],b[t].col);
}
int main(){
	scanf("%d%d",&n,&m);sz=pow(n,0.666666);
	for(int i=1;i<=n;++i){
		scanf("%d",&c[i]);
		d[++tot]=c[i];
	}
	for(int i=1;i<=m;++i){
		scanf("%s",opt);
		if(opt[0]=='Q'){
			al++;
			scanf("%d%d%d",&a[al].l,&a[al].r,&a[al].k);
			a[al].id=i;a[al].t=bl;
			d[++tot]=a[al].k;
		}
		else{
			bl++;
			scanf("%d%d",&b[bl].p,&b[bl].col);
			d[++tot]=b[bl].col;
		}
	}
	sort(d+1,d+tot+1);
	int len=unique(d+1,d+tot+1)-d-1;
	for(int i=1;i<=al;++i)a[al].k=lower_bound(d+1,d+len+1,a[al].k)-d;
	for(int i=1;i<=bl;++i)b[bl].col=lower_bound(d+1,d+len+1,b[bl].col)-d;
	for(int i=1;i<=n;++i)c[i]=lower_bound(d+1,d+len+1,c[i])-d;
	sort(a+1,a+al+1,cmp);
	for(int i=1;i<=al;++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(now<a[i].t)update(i,++now);
		while(now>a[i].t)update(i,now--);
		ans[a[i].id]=cnt[a[i].k];
	}
	for(int i=1;i<=al;++i)printf("%d\n",ans[i]);
	return 0;
}