40pts求调悬关

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int bel[N],a[N],c[N],t,w,los,n,k,ans,las,tot,A[N];
struct Node{int x,y,las,id;}f[N],x[N];
bool cmp(Node x,Node y){return bel[x.x]==bel[y.x]?x.y==y.y?x.las<y.las:(bel[x.x]&1?x.y<y.y:x.y>y.y):x.x<y.x;}
int get(){
	char ch=getchar();
	while (ch!='Q'&&ch!='R') ch=getchar();
	return (ch=='R'?1:0);
}
void cek(int x,int val){
	c[a[x]]+=val;
	if (!c[a[x]]&&val==-1) ans--;
	if (!(c[a[x]]-1)&&val==1) ans++;
}
void upd(int I,int x){
	if (f[x].x>=x[I].x&&f[x].x<=x[I].y) cek(f[x].y,1),cek(a[f[x].x],-1);
	swap(a[f[x].x],f[x].y);
}
signed main(){
	scanf("%d%d",&n,&k);int sq=(int)sqrt(n);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	for (int i=1;i<=k;i++){
		int ch=get();
		if (ch) las++,scanf("%d%d",&f[las].x,&f[las].y);
		else tot++,scanf("%d%d",&x[tot].x,&x[tot].y),bel[x[tot].x]=(x[tot].x-1)/sq,x[tot].las=las,x[tot].id=tot;
	}
	sort(x+1,x+tot,cmp);
	t=1;w=0;los=0;
	for (int i=1;i<=tot;i++){
		while (t<x[i].x) cek(t,-1),t++;
		while (t>x[i].x) t--,cek(t,1);
		while (w<x[i].y) w++,cek(w,1);
		while (w>x[i].y) cek(w,-1),w--;
		while (los<x[i].las) los++,upd(i,los);
		while (los>x[i].las) upd(i,los),los--;
		A[x[i].id]=ans;
	}
	for (int i=1;i<=tot;i++) printf("%d\n",A[i]);
	return 0;
}