P2464,40pts

#include<bits/stdc++.h>
#define INF 2e18
#define endl '\n'
#define pb push_back
#define fi first
#define se second
#define int long long
#define mem(x,v) memset(x,v,sizeof x)
using namespace std;
const int N = 1e5+5;
const int K = 1e3+5;

char op;
int n,m,bklen,bknum;
int a[N],st[K],ed[K],pos[N];
unordered_map <int,int> t[K];

void modify(int x,int k){
	t[pos[x]][a[x]]--;
	a[x]=k;
	t[pos[x]][a[x]]++;
}
int query(int x,int y,int k){
	int ans=0;
	if(pos[x]==pos[y]){
		for(int i=x;i<=y;i++)if(a[i]==k)ans++;
	}
	else{
		for(int i=x;i<=ed[pos[x]];i++)if(a[i]==k)ans++;
		for(int i=st[pos[y]];i<=y;i++)if(a[i]==k)ans++;
		for(int i=pos[x]+1;i<=pos[y]-1;i++)ans+=t[i][k];
	}
	return ans;
}
signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	bklen=sqrt(n),bknum=bklen+bool(n%bklen);
	for(int i=1;i<=bknum;i++){
		st[i]=(i-1)*bklen+1,ed[i]=min(n,i*bklen);
		for(int j=st[i];j<=ed[i];j++)pos[j]=i;
	}
	for(int i=1;i<=n;i++)cin>>a[i],t[pos[i]][a[i]]++;
	for(int i=1,x,y,z;i<=m;i++){
		cin>>op;
		if(op=='C')cin>>x>>y,modify(x,y);
		if(op=='Q')cin>>x>>y>>z,cout<<query(x,y,z)<<endl;
	}
	return 0;
}