https://www.luogu.com.cn/record/90331750

#include<bits/stdc++.h>
using namespace std;
pair<int,int> cg[133343];int tot;
struct QUE{int l,r,t,id;}q[133343];int blk;
long long res[133343];int tong[1000005],a[133343],cp[133343],orig[133343];
bool cmp(QUE x,QUE y){return x.l/blk==y.l-blk?(x.r/blk==y.r/blk?x.t<y.t:x.r<y.r):x.l<y.l;}
bool flg[133343];
inline void read(int &x)
{
   register int res=0;register char ch=getchar();
   while(ch<'0'||ch>'9')ch=getchar();
   while(ch>='0'&&ch<='9')res=(res<<1)+(res<<3)+(ch^48),ch=getchar();
   x=res;
}
int main()
{
   int n,m;read(n);read(m);blk=pow(n,0.66666);
   for(int i=1;i<=n;i++){read(a[i]);cp[i]=a[i];}
   for(int i=0;i<m;i++)
   {
   	scanf("%\n");
   	if(getchar()=='Q'){read(q[i].l);read(q[i].r);q[i].t=tot;q[i].id=i;flg[i]=1;}
   	else {tot++;read(cg[tot].first);read(cg[tot].second);orig[tot]=cp[cg[tot].first];cp[cg[tot].first]=cg[tot].second;}
   }
   sort(q,q+m,cmp);
   QUE pre;pre.l=1,pre.r=0;pre.t=0;long long cnt=0;
   for(int i=0;i<m;i++)
   {
   	if(!flg[q[i].id])continue;
   	if(q[i].l==q[i].r){res[q[i].id]=0;continue;}
   	while(pre.r<q[i].r)cnt+=tong[a[++pre.r]]++==0;
   	while(pre.l>q[i].l)cnt+=tong[a[--pre.l]]++==0;
   	while(pre.r>q[i].r)cnt-=--tong[a[pre.r--]]==0;
   	while(pre.l<q[i].l)cnt-=--tong[a[pre.l++]]==0;
   	while(pre.t<q[i].t)
   	{	
   		pre.t++;
   		if(cg[pre.t].first>=pre.l&&cg[pre.t].first<=pre.r)cnt-=--tong[a[cg[pre.t].first]]==0,cnt+=tong[cg[pre.t].second]++==0;
   		a[cg[pre.t].first]=cg[pre.t].second;
   	}
   	while(pre.t>q[i].t)
   	{
   		if(cg[pre.t].first>=pre.l&&cg[pre.t].first<=pre.r)cnt-=--tong[cg[pre.t].second]==0,cnt+=tong[orig[pre.t]]++==0;
   		a[cg[pre.t].first]=orig[pre.t];
   		pre.t--;
   	}
   	res[q[i].id]=cnt;
   }
   for(int i=0;i<m;i++)
   {
   	if(!flg[i])continue;
   	cout<<res[i]<<endl;
   }
}

https://www.luogu.com.cn/record/90331302

求助%%%