记录编号	477437	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]数颜色	最终得分	100
用户昵称	Hallmeow	是否通过	通过
代码语言	C++	运行时间	1.652 s
提交时间	2017-12-03 14:04:20	内存使用	50.21 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<set>
#include<vector>
using namespace std;
#define pos(i,a,b) for(int i=(a);i<=(b);i++)
#define N 10100
#define lc(x) (tree[x].lc)
#define rc(x) (tree[x].rc)
#include<algorithm>
int lowbit(int x){
	return x&(-x);
}
int n,m;
int a[N];
int pre[N],hou[N];
set<int> s[1001000];
vector<int> v[1001000];
int cnt[1001000],size;
struct haha{
	int lc,rc,sum;
}tree[N*100];
int root[N];
void update(int &rt,int pos,int num,int l,int r){
	if(!rt) rt=++size;
	if(l==r){
		tree[rt].sum+=num;return;
	}
	int mid=(l+r)>>1;
	if(pos<=mid) update(lc(rt),pos,num,l,mid);
	else update(rc(rt),pos,num,mid+1,r);
	tree[rt].sum=tree[lc(rt)].sum+tree[rc(rt)].sum;
}
void add(int x,int pos,int num){
	while(x<=n){
		update(root[x],pos,num,0,n);
		x+=lowbit(x);
	}
}
int cunx[100],cuny[100];
int query(int l,int r,int xl,int xr){
	int sumx(0),sumy(0);
	pos(i,1,cunx[0]) sumx+=tree[cunx[i]].sum;
	pos(i,1,cuny[0]) sumy+=tree[cuny[i]].sum;
	if(l>=xl&&r<=xr) return sumy-sumx;
	int ans(0);
	int mid=(l+r)>>1;
	int tempx[52],tempy[52];
	pos(i,0,cunx[0]) tempx[i]=cunx[i];
	pos(i,0,cuny[0]) tempy[i]=cuny[i];
	if(xl<=mid){
		pos(i,1,cunx[0]) cunx[i]=lc(cunx[i]);
		pos(i,1,cuny[0]) cuny[i]=lc(cuny[i]);
		ans+=query(l,mid,xl,xr);
		pos(i,0,tempx[0]) cunx[i]=tempx[i];
		pos(i,0,tempy[0]) cuny[i]=tempy[i];
	} 
	if(xr>mid){
		pos(i,1,cunx[0]) cunx[i]=rc(cunx[i]);
		pos(i,1,cuny[0]) cuny[i]=rc(cuny[i]);
		ans+=query(mid+1,r,xl,xr);
		pos(i,0,tempx[0]) cunx[i]=tempx[i];
		pos(i,0,tempy[0]) cuny[i]=tempy[i];
	} 
	return ans;
}
int Query(int x,int y){
	x--;
	cunx[0]=cuny[0]=0;
	int tx=x,ty=y;
	while(tx>0){
		cunx[++cunx[0]]=root[tx];tx-=lowbit(tx);
	}
	while(ty>0){
		cuny[++cuny[0]]=root[ty];ty-=lowbit(ty);
	}
	return query(0,n,0,x);
}
int main(){
	freopen("nt2011_color.in","r",stdin);
	freopen("nt2011_color.out","w",stdout);
	scanf("%d%d",&n,&m);
	pos(i,1,n){
		scanf("%d",&a[i]);
		pre[i]=0;hou[i]=n+1;
		if(!v[a[i]].empty()){
			pre[i]=v[a[i]][cnt[a[i]]-1];
			hou[v[a[i]][cnt[a[i]]-1]]=i;
		}
		v[a[i]].push_back(i);cnt[a[i]]++;
		s[a[i]].insert(i);
		add(i,pre[i],1);
	}
	pos(i,1,m){
		char c;cin>>c;
		int x,y;scanf("%d%d",&x,&y);
		if(c=='Q'){
			printf("%d\n",Query(x,y));
		}
		else{
			set<int>::iterator it1,it2,it3;
			it1=lower_bound(s[a[x]].begin(),s[a[x]].end(),x);
			if(s[a[x]].size()>1){
				if(it1==s[a[x]].begin()){
					add(x,0,-1);
					it2=++it1;it1--;
					add(*it2,x,-1);
					add(*it2,0,1);
				}
				else{
					if(it1==s[a[x]].end()){
						it2=--it1;it1++;
						add(x,*it2,-1);
					}
					else{
						it2=--it1;it1++;it3=++it1;it1--;
						add(*it3,x,-1);add(*it3,*it2,1);
						add(x,*it2,-1);
					}
				}
			}
			else{
				add(x,0,-1);
			}
			s[a[x]].erase(x);
			a[x]=y;
			s[y].insert(x);
			it1=lower_bound(s[y].begin(),s[y].end(),x);
			if(s[y].size()>1){
				if(it1==s[y].begin()){
					it2=++it1;it1--;
					add(*it2,0,-1);add(*it2,x,1);add(x,0,1);
				}
				else{
					if(it1==s[y].end()){
						it2=--it1;it1++;add(x,*it2,1);
					}
					else{
						it2=--it1;it1++;it3=++it1;it1--;
						add(*it3,*it2,-1);add(*it3,x,1);add(x,*it2,1);
					}
				}
			}
			else{
				add(x,0,1);
			}
		}
	}
	return 0;
}