悬关。

TLE on #2 & #8, 80 pts.

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
using pii=pair<int,int>;
#define fi first
#define se second
#ifdef ONLINE_JUDGE
	#define getchar getchar_unlocked
	#define putchar putchar_unlocked
#endif
template<typename Tp> Tp read() {
	Tp x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
template<typename Tp> void write(Tp x) {
	if(x<0) {putchar('-');x=-x;}
	static int sta[45];int top=0;
	do {sta[top++]=x%10;x/=10;} while(x);
	while(top) putchar(sta[--top]+'0');
}
constexpr int N=1e5+5;
int n,m,a[N],block,qtot,mtot,ans[N];
unordered_map<int,int> mp;
struct Query {
	int id,l,r,k,t;
	bool operator< (const Query &B) {
		if(l/block!=B.l/block) return l/block<B.l/block;
		else if(r/block!=B.r/block) return r/block<B.r/block;
		else return t<B.t;
	}
} qu[N];
struct Modify {
	int p,x;
} mo[N];
inline void add(int &x) {mp[x]++;}
inline void del(int &x) {mp[x]--;}
int main() {
	// ios::sync_with_stdio(false);
	// cin.tie(0);cout.tie(0);
	n=read<int>(),m=read<int>();
	for(register int i=1;i<=n;++i) a[i]=read<int>();
	for(register int i=1;i<=m;++i) {
		char op=getchar();
		while(op<'A'||op>'Z') op=getchar();
		if(op=='Q') {
			qtot++;
			qu[qtot].id=qtot,qu[qtot].t=mtot;
			qu[qtot].l=read<int>(),qu[qtot].r=read<int>(),qu[qtot].k=read<int>();
		}
		else {
			mtot++;
			mo[mtot].p=read<int>(),mo[mtot].x=read<int>();
		}
	}
	block=pow(n,2.0/3);
	sort(qu+1,qu+qtot+1);
	int l=1,r=0,lst=0;
	for(register int i=1;i<=qtot;++i) {
		while(l>qu[i].l) add(a[--l]);
		while(r<qu[i].r) add(a[++r]);
		while(l<qu[i].l) del(a[l++]);
		while(r>qu[i].r) del(a[r--]);
		while(lst<qu[i].t) {
			lst++;
			if(mo[lst].p>=l&&mo[lst].p<=r) {
				add(mo[lst].x);
				del(a[mo[lst].p]);
			}
			swap(mo[lst].x,a[mo[lst].p]);
		}
		while(lst>qu[i].t) {
			if(mo[lst].p>=l&&mo[lst].p<=r) {
				add(mo[lst].x);
				del(a[mo[lst].p]);
			}
			swap(mo[lst].x,a[mo[lst].p]);
			lst--;
		}
		ans[qu[i].id]=mp[qu[i].k];
	}
	for(register int i=1;i<=qtot;i++) {
		write<int>(ans[i]);
		putchar('\n');
	}
	return 0;
}