记录编号	601914	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	1901.[国家集训队2011]数颜色	最终得分	100
用户昵称	郑霁桓	是否通过	通过
代码语言	C++	运行时间	0.999 s
提交时间	2025-06-29 12:12:44	内存使用	7.53 MiB

#include<bits/stdc++.h>
using namespace std;
string ss;
int n,m,a[133335],xx,yy,l,r,p[1000005];
int qs,ts,as[133335],tq[133335];
int x[133335],y[133335],z[133335],tt;
struct qq{
    int x,y,t;
}q[133335];
bool c(qq x,qq y){
    if(x.x/2609==y.x/2609){
        if(x.y/2609==y.y/2609){
            return x.t<y.t;
        }
        return x.y<y.y;
    }
    return x.x<y.x;
}
int main(){
	freopen("nt2011_color.in","r",stdin);
	freopen("nt2011_color.out","w",stdout);
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=m;i++){
        cin>>ss>>xx>>yy;
        if(ss[0]=='Q') q[++qs].x=xx,q[qs].y=yy,q[qs].t=i,tq[i]=1;
        else x[i]=xx,y[i]=yy;
    }
    sort(q+1,q+qs+1,c);
    l=q[1].x,r=l-1;
    for(int i=1;i<=qs;i++){
        while(q[i].x<l) if(!(p[a[--l]]++)) ts++;
	    while(q[i].y>r) if(!(p[a[++r]]++)) ts++;
	    while(q[i].x>l) if(!(--p[a[l++]])) ts--;
	    while(q[i].y<r) if(!(--p[a[r--]])) ts--;
		while(q[i].t>tt){
       		tt++;
       		if(tq[tt]) continue;
            if(q[i].x<=x[tt]&&x[tt]<=q[i].y&&!--p[a[x[tt]]]) ts--;
            if(q[i].x<=x[tt]&&x[tt]<=q[i].y&&!p[y[tt]]++) ts++;
       		z[tt]=a[x[tt]];
       		a[x[tt]]=y[tt];
	   	}
        while(q[i].t<tt){
       		tt--;
       		if(tq[tt]) continue;
            if(q[i].x<=x[tt]&&x[tt]<=q[i].y&&!--p[a[x[tt]]]) ts--;
            if(q[i].x<=x[tt]&&x[tt]<=q[i].y&&!p[z[tt]]++) ts++;
       		a[x[tt]]=z[tt];
	   	}
        as[q[i].t]=ts;
    }
    for(int i=1;i<=m;i++) if(tq[i]) cout<<as[i]<<"\n";
    return 0;
}