#include<iostream>
#include<vector>
#include<math.h>
#include<algorithm>
using namespace std;
int cnt[2000000] = { 0 };
int a[200000];
int pos[200000];
int block, num;
int n, n1;
int ans = 0;
int aa[200000];
int qnum = 0, rnum = -1;
int l = 1, r = 0;
int now = -1;
long long c[200000];
vector<long long> b;//原数组
struct update {
	int pos;
	int data;
};
struct question {
	int L, R;
	int time;
	int num;
	int aim;
};
vector<update>u;
vector<question>q;
bool cmp(question q1, question q2) {
	if (pos[q1.L] != pos[q2.L]) return q1.L < q2.L;
	if (pos[q1.R] != pos[q2.R]) return q1.R < q2.R;
	return q1.time < q2.time;
}
void build() {
	for (int i = 1; i <= n; i++) {
		a[i] = lower_bound(b.begin(), b.end(), c[i]) - b.begin();
		pos[i] = num;
		if (i % block == 0) num++;
	}
	if (n % block == 0)num--;
}
void add(int x) {
	cnt[a[x]]++;
	if (cnt[a[x]] == 1) {
		ans++;
	}
}
void del(int x) {
	cnt[a[x]]--;
	if (cnt[a[x]] == 0) {
		ans--;
	}
}
void modify(int ti) {
	while (ti < now) {
		swap(u[now].data, a[u[now].pos]);
		if (u[now].pos >= l && u[now].pos <= r) {
			cnt[u[now].data]--;
			if (cnt[u[now].data] == 0)ans--;
			cnt[a[u[now].pos]]++;
			if (cnt[a[u[now].pos]] == 1)ans++;
		}
		now--;
	}
	while (ti > now) {
		now++;
		swap(u[now].data, a[u[now].pos]);
		if (u[now].pos >= l && u[now].pos <= r) {
			cnt[u[now].data]--;
			if (cnt[u[now].data] == 0)ans--;
			cnt[a[u[now].pos]]++;
			if (cnt[a[u[now].pos]] == 1)ans++;
		}
	}
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> n1;
	block = pow(n, 0.7);//注意是2.0/3.0，不是2/3
	for (int i = 1; i <= n; i++) {
		long long tmp;
		cin >> tmp;
		c[i] = tmp;
		b.push_back(tmp);
	}
	sort(b.begin(), b.end());
	b.erase(unique(b.begin(), b.end()), b.end());
	build();
a[0]=-1;
	for (int i = 0; i < n1; i++) {
		char op;
		cin >> op;
		if (op == 'Q') {
			question tmpq;
			long long aim;
			cin >> tmpq.L >> tmpq.R>>aim;
			tmpq.num = qnum;
			qnum++;
			tmpq.time = rnum;
			tmpq.aim = lower_bound(b.begin(), b.end(), aim) - b.begin();
if(b[tmpq.aim]!=aim)tmpq.aim=-1;			
q.push_back(tmpq);
		}
		else {
			update tmpu;
			long long data;
			cin >> tmpu.pos >> data;
			tmpu.data= lower_bound(b.begin(), b.end(), data) - b.begin();
			u.push_back(tmpu);
			rnum++;
		}
	}
	sort(q.begin(), q.end(), cmp);
	for (int i = 0; i < qnum; i++) {
		question tmpq;
		tmpq = q[i];
if(tmpq.aim==-1){aa[tmpq.num] = 0;continue;}
		int ti = tmpq.time;
		modify(ti);
		while (tmpq.L < l) {
			l--;
			add(l);
		}
		while (tmpq.R > r) {
			r++;
			add(r);
		}
		while (tmpq.L > l) {
if(l>0)
			del(l);
			l++;
		}
		while (tmpq.R < r) {
if(r<=n)
			del(r);
			r--;
		}
		aa[tmpq.num] = cnt[tmpq.aim];
	}
	for (int i = 0; i < qnum; i++) {
		cout << aa[i] << endl;
	}
	return 0;
}