这个小菜狗已经和第一篇题解对拍5000+组数据没有问题了

#include<bits/stdc++.h>
#define blk(i) ((i)/B)
using namespace std;
int a[233333],ans[233333],rec[1919810],s,cnt,T,n,m,B;
struct query
{
	int l,r,t,no;
	bool operator<(query a)
	{
		if(blk(l)^blk(a.l))return blk(l)<blk(a.l);
		if(blk(r)^blk(a.r))return blk(r)<blk(a.r);
		return t<a.t;
	}
}q[233333];
struct update
{
	int l,c;
}u[233333];
void add(int u)
{
	s+=!rec[u]++;
}
void del(int u)
{
	s-=!--rec[u];
}
void upd(int x,int t)
{
	if(q[x].l<=u[t].l&&u[t].l<=q[x].r)
	{
		del(a[u[t].l]);
		add(u[t].c);
	}
	swap(a[u[t].l],u[t].c);
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1,l,r;i<=m;i++)
	{
		string op;
		cin>>op>>l>>r;
		if(op=="Q")
		{
			cnt++;
			q[cnt]={l,r,T,cnt};
		}//据说q[++cnt]={l,r,T,cnt};会导致W&L不一致 
		else u[++T]={l,r};
	}
	B=max(cbrt(1ll*n*T),1.0);
	sort(q+1,q+cnt+1);
	int l,r,t;
	for(int i=1;i<=cnt;i++)
	{
		while(l>q[i].l)add(a[--l]);
		while(l<q[i].l)del(a[l++]);
		while(r>q[i].r)del(a[r--]);
		while(r<q[i].r)add(a[++r]);
		while(t<q[i].t)upd(i, ++t);
		while(t>q[i].t)upd(i, t--);
		ans[q[i].no]=s;
	}
	for(int i=1;i<=cnt;i++)cout<<ans[i]<<'\n';
}