全 WA 求调

#include<bits/stdc++.h>
using namespace std;
const int N=1.4e5+5,M=1e6+5;
int s;inline int id(int x){return (x+s-1)/s;}
struct Query{
	int l,r,t,idx;
	Query(int _l=1,int _r=0,int _t=0,int _idx=0){l=_l;r=_r;t=_t;idx=_idx;}
	inline bool operator<(const Query &A)const{
		if (id(l)!=id(A.l)) return id(l)<id(A.l);
		if (id(r)!=id(A.r)) return id(r)<id(A.r);
		if (t!=A.t) return t<A.t;
		return idx<A.idx;
	}
}q[N];
struct Update{int x,k;Update(int _x=0,int _k=0){x=_x;k=_k;}}u[N];
int n,m,v[N];
int cntu,cntq,ans[N];
int cnt[M],kind;
inline void del(int x){if (--cnt[x]==0) --kind;}
inline void add(int x){if (++cnt[x]==1) ++kind;}
inline void movetime(int l,int r,int now){
    int p=u[now].x;
    if (l<=p&&p<=r){
        del(v[p]);
        add(u[now].k);
    }
    swap(v[p],u[now].k);
}
inline void solve(){
	int l=1,r=0,t=0;
	for (int i=1;i<=cntq;i++){
		int ql=q[i].l,qr=q[i].r,qt=q[i].t;
		while (l<ql) del(v[l++]);
		while (l>ql) add(v[--l]);
		while (r<qr) add(v[++r]);
		while (r>qr) del(v[r--]);
		while (t<qt) movetime(l,r,++t);
		while (t>qt) movetime(l,r,t--);
		ans[q[i].idx]=kind;
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin>>n>>m;s=pow(n,2.0/3);
	for (int i=1;i<=n;i++) cin>>v[i];
	for (int i=1;i<=m;i++){
		char op;int l,r;
		cin>>op>>l>>r;
		if (op=='Q') q[++cntq]={l,r,cntu,cntq};
		else u[++cntu]={l,r};
	}
	sort(q+1,q+cntq+1);
	solve();
	for (int i=1;i<=cntq;i++)
		cout<<ans[i]<<'\n';
	return 0;
}