#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<map>
#include<unordered_map>
using namespace std;
const int N = 1e5 + 10;
int n,m;
int a,tot;
char op;
long long bk[N];
unordered_map<long long,long long> mp;
unordered_map<long long,long long> tr[N];

long long read(){
	long long num=0;
	int f=1;
	char ch = getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') f = -1;
		ch = getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		num = num * 10 + (ch^48);
		ch = getchar();
	}
	return num*f;
}
void write(long long x){
	if(x<0)
	{
		putchar('-');
		x = -x;
	}
	if(x>=10)
	{
		write(x/10);
	}
	putchar(x%10+48);
	return ;
}

int lowbit(int x){
	return x & (-x);
}
void add(int k,int x,int y){
	for(register int i=x;i<=n;i+=lowbit(i))
	{
		tr[i][k] += y;
	}
	return ;
}
long long query(int k,int x){
	long long res = 0;
	for(register int i=x;i>=1;i-=lowbit(i))
	{
		res += tr[i][k];
	}
	return res;
}
int main(){
	n = read();
	m = read();
	for(register int i=1;i<=n;i++)
	{
		a = read();
		if(!mp[a]) mp[a] = ++tot;
		bk[i] = mp[a];
		add(mp[a],i,1); 
	}
	for(register int i=1,a,b,k;i<=m;i++)
	{
		cin>>op;
		a = read();
		b = read();
		if(op=='Q')
		{
			k = read();
			
			write( query(mp[k],b) - query(mp[k],a-1) );
			puts("");
		}
		else if(op=='C')
		{
			add(bk[a],a,-1);
			add(mp[b],a,1);
			bk[a] = mp[b];
		}
	}
	return 0;
}