卡不动了，T 了三个点。

是不是块长和 cmp 写假了啊……

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>

#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
#define S1 200005
#define S2 1000005
#define _ read()

char buf[1<<21],*p1=buf,*p2=buf;

using std::sort;

struct ask
{
	int l,r,id,gsum;
}pro[S1],temp;

struct change
{
	int wh,lst,nxt;
}cge[S1],_temp;

int n,m,suma,sumc,lpos=1,rpos=0,ans,cgecnt,a[S1],cnt[S2],out[S1];
int blo;
int pt,l,r,i,id,gsum;

inline int read()
{
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')
		{
			w=-1;
		}
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		s=(s<<1)+(s<<3)+(ch^48);
		ch=getchar();
	}
	return s*w;
}

void print(int x)
{
	if(x==0)
	{
		return;
	}
	int t=x;
	if(t<0)
	{
		putchar('-');
		t=-t;
	}
	print(t/10);
	putchar(t%10+48);
}

inline bool cmp(ask &x,ask &y)
{
	if(x.l/blo==y.l/blo)
	{
		if((x.l/blo)&1)
		{
			return x.r>y.r; 
		}
		return x.r<y.r;
	}
	return x.l<y.l;
}

inline void add(int x)
{
	ans+=!cnt[a[x]]++;
}

inline void del(int x)
{
	ans-=!--cnt[a[x]];
}

inline void upd(int type)
{
	if(type==-1)
	{
		pt=cge[cgecnt].wh;
		if(pt>=lpos&&pt<=rpos)
		{
			ans-=--cnt[a[pt]]==0;
		}
		a[pt]=cge[cgecnt].lst;
		if(pt>=lpos&&pt<=rpos)
		{
			ans+=++cnt[a[pt]]==1;
		}
	}
	cgecnt+=type;
	if(type==1)
	{
		pt=cge[cgecnt].wh;
		if(pt>=lpos&&pt<=rpos)
		{
			ans-=--cnt[a[pt]]==0;
		}
		a[pt]=cge[cgecnt].nxt;
		if(pt>=lpos&&pt<=rpos)
		{
			ans+=++cnt[a[pt]]==1;
		}
	}
}

int main()
{
	n=_;
	m=_;
	for(int i=1;i<=n;++i) a[i]=_;
	for(i=1;i<=m;++i)
	{
		char opt=getchar();
		while(opt!='Q'&&opt!='R')
		{
			opt=getchar();
		}
		if(opt=='Q')
		{
			l=_;
			r=_;
			temp={l,r,++suma,sumc};
			pro[suma]=temp;
		}
		else
		{
			int p=_;
			int x=_;
			_temp={p,a[p],x};
			a[p]=x;
			cge[++sumc]=_temp;
		}
	}
	for(i=sumc;i>=1;--i) a[cge[i].wh]=cge[i].lst;
	blo=pow(n,0.66666);
	sort(pro+1,pro+suma+1,cmp);
	for(i=1;i<=suma;++i)
	{
		l=pro[i].l,r=pro[i].r,id=pro[i].id,gsum=pro[i].gsum;
		while(lpos<l) del(lpos++);
		while(rpos>r) del(rpos--);
		while(lpos>l) add(--lpos);
		while(rpos<r) add(++rpos);
		while(gsum>cgecnt) upd(1);
		while(gsum<cgecnt) upd(-1);
		out[id]=ans;
	}
	for(i=1;i<=suma;++i) {print(out[i]);putchar('\n');}
	return 0;
}