#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
int n, m, len, a[N], b[N << 1], ans[N];
int ver, cnt, blk, p[N], num[N], tot[N << 1];
struct query{
	int l, r, k, v, id;
	bool operator < (const query &p) const {
		if(l / blk != p.l / blk)
			return l / blk < p.l / blk;
		if(r / blk != p.r / blk)
			return r / blk < p.r / blk;
		return v < p.v;
	}
} q[N];

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

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

void update(int x, int l, int r){//只统计当前这次修改对 [l,r] 的贡献
	if(l <= p[x] && p[x] <= r){
		del(a[p[x]]);
		add(num[x]);
	}
	swap(a[p[x]], num[x]);//如果不在该区间内，就只用修改，不用统计了 
}

int main(){
	scanf("%d%d", &n, &m);
	for(int i=1;i<=n;i++)
		scanf("%d", &a[i]), b[++len] = a[i];
	for(int i=1;i<=m;i++){
		char op[4];
		scanf("%s", op);
		if(op[0] == 'Q'){
			int l, r, k;
			scanf("%d%d%d", &l, &r, &k);
			q[++cnt] = (query){l, r, k, ver, i};
		}
		else if(op[0] == 'C'){
			++ver;
			scanf("%d%d", &p[ver], &num[ver]);
			b[++len] = num[ver];
		}
	}
	sort(b + 1, b + 1 + len);
	len = unique(b + 1, b + 1 + len) - b - 1;
	for(int i=1;i<=n;i++)
		a[i] = lower_bound(b + 1, b + 1 + len, a[i]) - b;
	for(int i=1;i<=ver;i++)
		num[i] = lower_bound(b + 1, b + 1 + len, num[i]) - b;
	for(int i=1;i<=cnt;i++)
		q[i].k = lower_bound(b + 1, b + 1 + len, q[i].k) - b;
	
	blk = pow(n + m, 2.0 / 3.0);
	sort(q + 1, q + 1 + cnt);
	int s = 1, t = 0, c = 0;
	for(int i=1;i<=cnt;i++){
		while(s > q[i].l)
			add(a[--s]);
		while(t < q[i].r)
			add(a[++t]);
		while(s < q[i].l)
			del(a[s++]);
		while(t > q[i].r)
			del(a[t--]);
		while(c < q[i].v)
			update(++c, q[i].l, q[i].r);//只添加了这两句话
		while(c > q[i].v)
			update(c--, q[i].l, q[i].r);//只添加了这两句话 
		 ans[q[i].id] = tot[q[i].k];
	}
	for(int i=1;i<=cnt;i++)
		printf("%d\n", ans[i]);
	return 0;
}