#include<bits/stdc++.h>
using namespace std;
inline int read()
{
	char x=getchar();
	int ans=0,f=1;
	while(x<'0'||x>'9')
	{
		if(x=='-')
			f=-f;
		x=getchar();
	}
	while(x>='0'&&x<='9')
	{
		ans=(ans<<3)+(ans<<1)+x-'0';
		x=getchar();
	}
	return ans*f;
}	
int n,m,h,len;
int a[100010];
int belong[100010];
vector<int> b[1010];
void init()
{
	for(register int i=1;i<=n;i++)
		b[belong[i]].push_back(a[i]);
	for(register int i=1;i<=len;i++)
		sort(b[i].begin(),b[i].end());
}
int find1(int x,int k)
{
	int l=0,r=b[x].size()-1,ans=b[x].size();
	while(l<=r)
	{
		int mid=(l+r)>>1;
		if(b[x][mid]>=k)
		{
			ans=mid;
			r=mid-1;
		}
		else
			l=mid+1;
	}
	return ans;
}
int find2(int x,int k)
{
	int l=0,r=b[x].size()-1,ans=b[x].size();
	while(l<=r)
	{
		int mid=(l+r)>>1;
		if(b[x][mid]>k)
		{
			ans=mid;
			r=mid-1;
		}
		else
			l=mid+1;
	}
	return ans;
}
void change(int x,int y)
{
	int id=belong[x];
	b[id].erase(b[id].begin()+find1(id,a[x]));
	a[x]=y;
	b[id].insert(b[id].begin()+find1(id,a[x]),a[x]);
}
int query(int l,int r,int k)
{
	int idl=belong[l],idr=belong[r];
	int ans=0;
	if(idl==idr)
	{
		for(register int i=l;i<=r;i++)
			if(a[i]==k)
				ans++;
	}
	else
	{
		for(register int i=l;belong[i]==idl;i++)
			if(a[i]==k)
				ans++;
		for(register int i=r;belong[i]==idr;i--)
			if(a[i]==k)
				ans++;
		for(register int i=idl+1;i<idr;i++)
			ans+=find2(i,k)-find1(i,k);
	}
	return ans;
}
int main()
{
	n=read(),m=read();
	h=sqrt(n);
	len=ceil(n*1.0/h);
	for(register int i=1;i<=n;i++)
	{
		a[i]=read();
		belong[i]=(i-1)/h+1;
	}
	init(); 
	for(register int i=1;i<=m;i++)
	{
		char ch=0; 
		while(ch!='C'&&ch!='Q')
			ch=getchar();
		if(ch=='Q')
		{
			int x=read(),y=read(),k=read();
			printf("%d\n",query(x,y,k));
		}
		else
		{
			int x=read(),y=read();
			change(x,y);
		}
	}
	return 0;
}

这个程序我认为是 $O(n \times sqrt(n) \times log(n)$