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

#define Troy

#include <bits/stdc++.h>

using namespace std;

inline int read(){
    int s=0,k=1;char ch=getchar();
    while(ch<'0'|ch>'9')    ch=='-'?k=-1:0,ch=getchar();
    while(ch>47&ch<='9')    s=s*10+(ch^48),ch=getchar();
    return s*k;
}

const int N=1.1e4+5;

short c[N][N];

set<int> a[N];
set<int>::iterator it,nxt;

int Hash[N*100],n,m,cnt,val[N];

inline int lowbit(int x){
    return x&(-x);
}

inline void add(int x,int y,int w){
    for(int i=x;i<=n;i+=lowbit(i))
        for(int j=y;j<=n;j+=lowbit(j))
            c[i][j]+=w;
}

inline int query(int x,int y){
    int ret=0;
    for(int i=x;i;i-=lowbit(i))
        for(int j=y;j;j-=lowbit(j))
            ret+=c[i][j];
    return ret;
}

int Main(void){
    freopen("nt2011_color.in","r",stdin);
    freopen("nt2011_color.out","w",stdout);
    n=read(),m=read();
    for(int i=1;i<=n;++i){
        int x=read();
        if(!Hash[val[i]=x])    Hash[x]=++cnt,a[cnt].insert(0);
        it=a[Hash[x]].end();
        --it;
        add(i,(*it)+1,1);
        a[Hash[x]].insert(i);
    }
    char opt[3];
    int x,y,pos;
    while(m--){
        scanf("%s",opt);x=read(),y=read();
        if(opt[0]=='Q'){
            printf("%d\n",query(y,x)-query(x-1,x));
        }else{
            nxt=it=a[Hash[val[x]]].find(x);
            --it;
            ++nxt;
            add(x,(*it)+1,-1);
            // printf("pre=%d\n",(*it));
            if(nxt!=a[Hash[val[x]]].end())
                add(*nxt,x+1,-1),add(*nxt,(*it)+1,1);//,printf("nxt=%d\n",*nxt);
            a[Hash[val[x]]].erase(x);
            val[x]=y;
            if(!Hash[val[x]])   Hash[y]=++cnt,a[cnt].insert(0);
            a[Hash[val[x]]].insert(x);
            nxt=it=a[Hash[val[x]]].find(x);
            --it;
            ++nxt;
            add(x,(*it)+1,1);
            // printf("pre=%d\n",*it);
            if(nxt!=a[Hash[val[x]]].end())
                add(*nxt,x+1,1),add(*nxt,(*it)+1,-1);//,printf("nxt=%d\n",*nxt);
        }
    }
}

int s=Main();

int main(){
    ;
    return 0;
}