记录编号	477981	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]数颜色	最终得分	100
用户昵称	Hzoi_moyi	是否通过	通过
代码语言	C++	运行时间	0.447 s
提交时间	2017-12-07 21:12:46	内存使用	24.03 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<set>
using namespace std;
inline int read()
{
	int jg=0,jk=getchar()-'0';
	while(jk<0||jk>9)    jk=getchar()-'0';
	while(jk>=0&&jk<=9)  jg*=10,jg+=jk,jk=getchar()-'0';
	return jg;
}
const int sj=10010;
set<int>  kn[sj<<1];
int n,m,a[sj],op[sj],ls[sj<<1],a1[sj],a2[sj],cnt,tot,N,M,L[sj],R[sj],rt[sj],nt,pr;
char s[5];
set<int>::iterator it;
inline int lowbit(int x)
{
	return x&(-x);
}
struct tree
{
	int lc,rc,sum;
}t[sj*200];
void update(int x,int &y,int l,int r,int pos,int op)
{
	y=++tot;
	t[y].lc=t[x].lc,t[y].rc=t[x].rc,t[y].sum=t[x].sum+op;
	//cout<<"QAQ"<<pos<<" "<<l<<" "<<r<<" "<<t[y].sum<<endl;
	if(l==r)  return;
	int mid=l+r>>1;
	if(pos<=mid)  update(t[x].lc,t[y].lc,l,mid,pos,op);
	else          update(t[x].rc,t[y].rc,mid+1,r,pos,op);
}
void bit_update(int x,int y,int op)
{
	while(x<=n)
	    update(rt[x],rt[x],0,n,y,op),x+=lowbit(x);
}
int query(int l,int r,int y)
{   
    int ret=0;
	if(r==y)  
	{    
	    for(int i=1;i<=N;i++)  ret-=t[L[i]].sum;
	    for(int i=1;i<=M;i++)  ret+=t[R[i]].sum;
	    //cout<<l<<" "<<r<<" "<<ret<<endl;
		return ret;
    }
    int mid=l+r>>1;
    if(y<=mid)  
    {
    	for(int i=1;i<=N;i++)  L[i]=t[L[i]].lc;
    	for(int i=1;i<=M;i++)  R[i]=t[R[i]].lc;
	    return query(l,mid,y);
	}
	for(int i=1;i<=N;i++)  ret-=t[t[L[i]].lc].sum,L[i]=t[L[i]].rc;
	for(int i=1;i<=M;i++)  ret+=t[t[R[i]].lc].sum,R[i]=t[R[i]].rc;
	//cout<<l<<" "<<r<<" "<<ret<<"@"<<endl;
	return ret+query(mid+1,r,y);
}
int bit_query(int x,int y)
{
	N=M=0;
	int ox=x;
	while(x>0)
	   L[++N]=rt[x],x-=lowbit(x);
	while(y>0)
	   R[++M]=rt[y],y-=lowbit(y);
	return query(0,n,ox);
}
void build(int &x,int z,int y)
{
	x=++tot;
	if(z==y)  return;
	int mid=z+y>>1;
	build(t[x].lc,z,mid),build(t[x].rc,mid+1,y);
}
int main()
{
	//freopen("t.txt","r",stdin);
	freopen("nt2011_color.in","r",stdin);
	freopen("nt2011_color.out","w",stdout);
    n=read(),m=read();
    for(int i=1;i<=n;i++)  
		a[i]=read(),ls[++cnt]=a[i];
	for(int i=1;i<=m;i++)
	{
		scanf("%s",s);
		if(s[0]=='Q')  op[i]=1;
		else           op[i]=0;
		a1[i]=read(),a2[i]=read();
		if(op[i]==0)   ls[++cnt]=a2[i];
	}
	sort(ls+1,ls+cnt+1);
	cnt=unique(ls+1,ls+cnt+1)-ls-1;
	build(rt[0],0,n);
	for(int i=1;i<=n;i++)
	{
		a[i]=lower_bound(ls+1,ls+cnt+1,a[i])-ls;
		kn[a[i]].insert(0),kn[a[i]].insert(n+1);
		it=kn[a[i]].lower_bound(i),it--;
	    bit_update(i,*it,1);
	    kn[a[i]].insert(i);
    }
    for(int i=1;i<=m;i++)
    {
    	if(op[i]==1)
    	    printf("%d\n",bit_query(a1[i]-1,a2[i]));
    	else
    	{
    		a2[i]=lower_bound(ls+1,ls+cnt+1,a2[i])-ls;
    		if(a[a1[i]]==a2[i])  continue;
    		it=kn[a[a1[i]]].lower_bound(a1[i]);
    		it--,pr=*it,it++,it++,nt=*it;
    		bit_update(a1[i],pr,-1);
    		if(nt<=n)  
			{    
				bit_update(nt,a1[i],-1);
		        bit_update(nt,pr,1);
			}
			kn[a[a1[i]]].erase(a1[i]);
    		a[a1[i]]=a2[i];
    		kn[a[a1[i]]].insert(0),kn[a[a1[i]]].insert(n+1);
    		it=kn[a[a1[i]]].lower_bound(a1[i]);
    		nt=*it,it--,pr=*it;
    		bit_update(a1[i],pr,1);
    		if(nt<=n)
    		{
    			bit_update(nt,pr,-1);
    			bit_update(nt,a1[i],1);
			}
    		kn[a[a1[i]]].insert(a1[i]);
		}
	}
	return 0;
}