C++(clang++11) 解法, 执行用时: 17ms, 内存消耗: 4632K, 提交时间: 2020-12-10 12:49:10

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define debug(x) cerr<<#x<<" = "<<x
#define sp <<"  "
#define el <<endl
#define fgx cerr<<" ----------------------------------- "<<endl
#define pii pair<int,int>
#define ULL unsigned long long
#define DB double
#define uint unsigned int
#define pb push_back
#define mpt make_pair
#define fr first
#define sc second
inline int read(){
	int nm=0,fh=1; char cw=getchar();
	for(;!isdigit(cw);cw=getchar()) if(cw=='-') fh=-1;
	for(;isdigit(cw);cw=getchar()) nm=nm*10+(cw-'0');
	return nm*fh;
}
#define M 200020
#define MAXN 1000020
int n,m,K,a[M],blg[M],res; pii sta[M];
int top,tail,cnt[MAXN],L,R,nowtms;
LL ans[M];
struct Query{int l,r,tms,id;}que[M];
inline bool cmp(Query a,Query b){
	if(blg[a.l]^blg[b.l]) return blg[a.l]<blg[b.l];
	if(blg[a.r]^blg[b.r]) return blg[a.r]<blg[b.r];
	return a.tms<b.tms;
}
inline void ins(int x){cnt[x]++; if(cnt[x]==1) res++;}
inline void ers(int x){--cnt[x]; if(!cnt[x]) --res;}
inline void chg(int now){
	int x=sta[now].fr;
	if(L<=x&&x<=R) ers(a[x]);
	swap(a[x],sta[now].sc);
	if(L<=x&&x<=R) ins(a[x]);
}

int main(){
	n=read(),m=read(),K=max((int)pow(n,0.666666),1);
	for(int i=1;i<=n;i++) a[i]=read(),blg[i]=(i-1)/K+1;
	for(int i=1,x,y;i<=m;i++){
		char op[15]; scanf("%s",op);
		if(op[0]=='Q') x=read(),y=read(),top++,que[top]=(Query){x,y,tail,top};
		else x=read(),y=read(),sta[++tail]=mpt(x,y);
	}
	sort(que+1,que+top+1,cmp);
	L=1,R=0,nowtms=0;
	for(int i=1;i<=top;i++){
		while(L>que[i].l) ins(a[--L]);
		while(R<que[i].r) ins(a[++R]);
		while(L<que[i].l) ers(a[L++]);
		while(R>que[i].r) ers(a[R--]);
		while(nowtms<que[i].tms) chg(++nowtms);
		while(nowtms>que[i].tms) chg(nowtms--);
		ans[que[i].id]=res;
	}
	for(int i=1;i<=top;i++) printf("%d\n",ans[i]);
	return 0;
}