#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5;
int a[N],ans[N], belong[N],cnt[N];
struct node {
	int l, r, time, w;
	int k;
} q[N];
struct changed {
	int pos, color, last;
} c[N];
int cntq, cntc, n, m, block;
vector<int >v;
int cmp(node a, node b) {
return (a.l/block)==(b.l/block)?(a.r/block)==(b.r/block)?a.time<b.time:a.r<b.r:a.l<b.l;
}
signed main() {
	scanf("%lld%lld",&n,&m);
	block=pow(n,2.0/3.0);
	for(int i=1; i<=n; ++i)
		scanf("%lld",&a[i]),v.push_back(a[i]);
	sort(v.begin(),v.end());
	v.erase(unique(v.begin(), v.end()),v.end());
	for(int i=1; i<=n; i++)
		a[i]=lower_bound(v.begin(),v.end(),a[i])-v.begin()+1;
	for(int i=1; i<=m; ++i) {
		char opt;
		int l,r,k;
		cin>>opt;
		scanf("%lld%lld",&l,&r);
		if(opt=='Q') {
			cin>>k;
			k=lower_bound(v.begin(),v.end(),k)-v.begin()+1;
			q[++cntq].l=l;
			q[cntq].r=r;
			q[cntq].k=k;
			q[cntq].time=cntc;
			q[cntq].w= cntq;
		} else {
			r=lower_bound(v.begin(),v.end(),r)-v.begin()+1;
			c[++cntc].pos=l;
			c[cntc].color=r;
		}
	}
	sort(q+1,q+cntq+1,cmp);
	int l=1,r=0,time=0;
	for(int i=1; i<=cntq; ++i) {
		int ql=q[i].l,qr=q[i].r,qt=q[i].time;
		while(l<ql)--cnt[a[l++]];
		while(l>ql)cnt[a[--l]]++;
		while(r<qr)cnt[a[++r]]++;
		while(r>qr)--cnt[a[r--]];
		while(time<qt) {
			++time;
			if(ql<=c[time].pos&&c[time].pos<=qr)--cnt[a[c[time].pos]],cnt[c[time].color]++;
			swap(a[c[time].pos],c[time].color);
		}
		while(time>qt) {
			if(ql<=c[time].pos&&c[time].pos<=qr)--cnt[a[c[time].pos]],cnt[c[time].color]++;
			swap(a[c[time].pos],c[time].color);
			--time;
		}
		ans[q[i].w]=cnt[q[i].k];
	}
	for(int i=1; i<=cntq; ++i)
		printf("%lld\n",ans[i]);
	return 0;
}