记录编号	192449	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]数颜色	最终得分	100
用户昵称	stdafx.h	是否通过	通过
代码语言	C++	运行时间	0.825 s
提交时间	2015-10-11 06:30:34	内存使用	12.03 MiB

//algorithm::segtree with treap + treap   --by stdafx

#define lson l,m,t
#define rson m+1,r,t|1

#define MAXN 10010UL
#define MAXL 10UL

#include <cstdio>
#include <ctime>
#include <cstdlib>

struct Treap_Node{
	Treap_Node *left,*right;
	int val,fix,s;
	Treap_Node(){
		left=NULL,right=NULL;
	}
};

Treap_Node *tree[MAXN<<2],*color_tree[MAXN*100];
int n,m,seq[MAXN],Ans,Check_Val,posl,posr,color_pre[MAXN*100],pre[MAXN],update_pos,color_next[MAXN*100],Next[MAXN],before_val,after_val;
char query[MAXL];

inline int in(){
	int x=0,c=getchar();
	while(c<'0'||c>'9') c=getchar();
	for(;c>='0'&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+c-48;
	return x;
}

inline void Update_Treap_Node(Treap_Node *&p){
	if(!p) return;
	p->s=1;
	if(p->left) p->s+=p->left->s;
	if(p->right) p->s+=p->right->s;
	return;
}

inline void LeftTurn(Treap_Node *&a){
	Treap_Node *b=a->right;
	a->right=b->left;b->left=a;a=b;
	Update_Treap_Node(b->left);
	return;
}

inline void RightTurn(Treap_Node *&a){
	Treap_Node *b=a->left;
	a->left=b->right;b->right=a;a=b;
	Update_Treap_Node(b->right);
	return;
}

int Find(Treap_Node *p,int val){
	if(!p) return 0;
	if(p->val<val){
		int tmp=Find(p->right,val)+1;
		if(p->left) return p->left->s+tmp;
		else return tmp;
	}
	else return Find(p->left,val);
}

void Insert(Treap_Node *&p,int val){
	if(!p){
		p=new Treap_Node();
		p->val=val;p->fix=rand();p->s=1;
	}
	else if(val<=p->val){
		Insert(p->left,val);
		if((p->left->fix)<(p->fix)) RightTurn(p);
	}
	else{
		Insert(p->right,val);
		if((p->right->fix)<(p->fix)) LeftTurn(p);
	}
	Update_Treap_Node(p);
	return;
}

void Delete(Treap_Node *&p,int val){
	if(val==p->val){
		if((!p->left)||(!p->right)){
			Treap_Node *t=p;
			if(p->left) p=p->left;
			else p=p->right;
			delete t;
		}
		else{
			if((p->left->fix)<(p->right->fix)) RightTurn(p),Delete(p->right,val);
			else LeftTurn(p),Delete(p->left,val);
		}
	}
	else if(val<p->val) Delete(p->left,val);
	else Delete(p->right,val);
	Update_Treap_Node(p);
	return;
}

void Build(int l,int r,int rt){
	for(int i=l;i<=r;i++){
		Insert(tree[rt],pre[i]);
	}
	if(l==r) return;
	int m=(l+r)>>1,t=rt<<1;
	Build(lson);Build(rson);
	return;
}

void Update(int l,int r,int rt){
	Delete(tree[rt],before_val);
	Insert(tree[rt],after_val);
	if(l==r) return;
	int m=(l+r)>>1,t=rt<<1;
	if(update_pos<=m) Update(lson);
	if(update_pos>m) Update(rson);
	return;
}

void Query(int l,int r,int rt){
	if(posl<=l&&posr>=r){
		Ans+=Find(tree[rt],Check_Val);
		return;
	}
	int m=(l+r)>>1,t=rt<<1;
	if(posl<=m) Query(lson);
	if(posr>m) Query(rson);
	return;
}

inline void QUERY(int L,int R){
	Ans=0;Check_Val=L;
	posl=L;posr=R;
	Query(1,n,1);
	printf("%d\n",Ans);
	return;
}

int find_Last(Treap_Node *p,int val){
	if(!p) return 0;
	if(p->val>val){
		int find_l=find_Last(p->left,val);
		if(find_l) return find_l;
		else return p->val;
	}
	return find_Last(p->right,val);
}

int find_Smaller(Treap_Node *p,int val){
	if(!p) return 0;
	if(p->val<val){
		int find_l=find_Smaller(p->right,val);
		if(find_l) return find_l;
		else return p->val;
	}
	return find_Smaller(p->left,val);
}

inline void MODIFY(int now_pos,int new_color){
	if(seq[now_pos]==new_color) return;
	int r_color=seq[now_pos];
	Delete(color_tree[r_color],now_pos);
	if(pre[now_pos]) Next[pre[now_pos]]=Next[now_pos];
	if(Next[now_pos]){
		int next_r_pos=Next[now_pos];
		pre[next_r_pos]=pre[now_pos];
		if(pre[now_pos]) Next[pre[now_pos]]=next_r_pos;
		update_pos=next_r_pos;
		before_val=now_pos;after_val=pre[now_pos];Update(1,n,1);
	}
	int new_after=find_Last(color_tree[new_color],now_pos),ready_update=0;
	if(new_after){
		if(pre[new_after]) Next[pre[new_after]]=now_pos,ready_update=pre[new_after];
		update_pos=new_after;before_val=pre[new_after];after_val=now_pos;Update(1,n,1);
		pre[new_after]=now_pos;
	}
	if(!ready_update) ready_update=find_Smaller(color_tree[new_color],now_pos);
	Next[ready_update]=now_pos;
	Next[now_pos]=new_after;
	before_val=pre[now_pos];
	pre[now_pos]=ready_update;
	update_pos=now_pos;after_val=ready_update;Update(1,n,1);
	seq[now_pos]=new_color;
	Insert(color_tree[new_color],now_pos);
	return;
}

int main(){
	freopen("nt2011_color.in","r",stdin);freopen("nt2011_color.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		seq[i]=in();pre[i]=color_pre[seq[i]];color_pre[seq[i]]=i;Insert(color_tree[seq[i]],i);
	}
	for(int i=n;i>0;i--){
		Next[i]=color_next[seq[i]];color_next[seq[i]]=i;
	}
	Build(1,n,1);
	for(int i=1,a,b;i<=m;i++){
		scanf("%s",query);a=in();b=in();
		if(query[0]=='Q') QUERY(a,b);
		else MODIFY(a,b);
	}
	return 0;
}