记录编号	421842	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	1901.[国家集训队2011]数颜色	最终得分	100
用户昵称	~玖湫~	是否通过	通过
代码语言	C++	运行时间	0.170 s
提交时间	2017-07-08 10:52:36	内存使用	4.33 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;
const int M=10000+1000;
const int qrt=100;
int n,m,nt,ans,bl;
int val[M],beg[qrt+10],bend[qrt+10],color[M],block[M],cnt[M];
int f[qrt+10][qrt+10],g[qrt+10][M];
bool pd[M];
map<int,int> mp;
inline int read(){
       int x=0,f=1;char ch=getchar();
       while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
       while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
       return x*f;
}
inline void init(){
    for(int i=1;i<=bl;i++) beg[i]=(i-1)*qrt+1,bend[i]=min(n,i*qrt);
    for(int i=1;i<=bl;i++){
       int an=0;int bh=i;
       for(int j=beg[i];j<=n;j++){
         if(!pd[val[j]])
           an++,pd[val[j]]=1;
         if(j==bend[bh]){
           f[i][bh]=an;
           //cout<<"i="<<i<<" bh= "<<bh<<" f="<<an<<endl;
           bh++;
         }
       }
       memset(pd,0,sizeof(pd));
    }
	for(int i=1;i<=bl;i++){
		for(int j=1;j<=nt;j++) g[i][j]=g[i-1][j];
		for(int j=beg[i];j<=bend[i];j++) g[i][val[j]]++;
	}
}
inline int query(int l,int r){
	ans=0;
	if(block[l]==block[r]){
		for(int i=l;i<=r;i++) cnt[val[i]]=0;
		for(int i=l;i<=r;i++){
			cnt[val[i]]++;
			if(cnt[val[i]]==1)
				ans++;
		}
		return ans;
	}
	memset(pd,0,sizeof(pd));
	if(block[r]-block[l]>1) ans=f[block[l]+1][block[r]-1];
	for(int i=l;i<=bend[block[l]];i++)
		if(!pd[val[i]]&&g[block[r]-1][val[i]]==g[block[l]][val[i]])
			ans++,pd[val[i]]=1;
	for(int i=beg[block[r]];i<=r;i++)
        if(!pd[val[i]]&&g[block[r]-1][val[i]]==g[block[l]][val[i]])
			ans++,pd[val[i]]=1;
	return ans;
}
inline void change(int pos,int to){
	int blo=block[pos],from=val[pos];
	val[pos]=to;
	for(int i=blo;i<=bl;i++) g[i][from]--,g[i][to]++;
	for(int i=1;i<=blo;i++)
		for(int j=blo;j<=bl;j++){
			if(g[j][from]-g[i-1][from]==0)
				f[i][j]--;
			if(g[j][to]-g[i-1][to]==1)
				f[i][j]++;
	    }
}
int DK(){
    //freopen("a.in","r",stdin);
    //freopen("a.out","w",stdout);
    freopen("nt2011_color.in","r",stdin);
    freopen("nt2011_color.out","w",stdout);
    n=read();m=read();
    for(int i=1;i<=n;i++){
      val[i]=read();
      block[i]=(i-1)/qrt+1;
      if(mp.count(val[i])){
        color[mp[val[i]]]=val[i];
        val[i]=mp[val[i]];
      }
      else{
        nt++;
        color[nt]=val[i];
        mp[val[i]]=nt;
        val[i]=nt;
      }
    }
    bl=block[n];
    init();
    int le,ri;
    char s[2];
    while(m--){
      scanf("%s",s);
      le=read();ri=read();
      if(s[0]=='Q')
        printf("%d\n",query(le,ri));
      else{
		if(!mp.count(ri)){
			nt++;
			color[nt]=ri;
			mp[ri]=nt;
			//val[le]=nt;
		}
        change(le,mp[ri]);
	  }
    }
    //while(1);
    return 0;
}
int dk=DK();
int main(){
    ;
}