1 #include<cstdio> 2 #include<cmath> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 int n,m,sz,sum,l[30],r[30],num[10001],pre[10001],preb[10001],a[10001],x,y,pos[1000001]; 7 int Res,Num;char C,CH[12]; 8 inline int G() 9 {10     Res=0;C=‘*‘; 11     while(C<‘0‘||C>‘9‘)C=getchar();12     while(C>=‘0‘&&C<=‘9‘){Res=Res*10+(C-‘0‘);C=getchar();}13     return Res;14 }15 inline void P(int x)16 {17     Num=0;if(!x){putchar(‘0‘);puts("");return;}18     while(x>0)CH[++Num]=x%10,x/=10;19     while(Num)putchar(CH[Num--]+48);20     puts("");21 }22 void makeblock()23 {24     sz=sqrt((double)n*log2(n)); if(!sz) sz=1;25     for(sum=1;sum*sz<n;sum++)26       {27         l[sum]=(sum-1)*sz+1;28         r[sum]=sum*sz;29           for(int i=l[sum];i<=r[sum];i++)30           num[i]=sum;31       }32     l[sum]=sz*(sum-1)+1;33     r[sum]=n;34     for(int i=l[sum];i<=r[sum];i++)35       num[i]=sum;36 }37 void makepre()38 {39     for(int i=1;i<=n;i++) {pre[i]=pos[a[i]]; pos[a[i]]=i;}40     memcpy(preb,pre,sizeof(pre));41     for(int i=1;i<=sum;i++) sort(pre+l[i],pre+r[i]+1);42 }43 inline void query()44 {45     int res=0;46     if(num[x]+1>=num[y]) {for(int i=x;i<=y;i++) if(preb[i]<x) res++;}47     else48       {49           for(int i=x;i<=r[num[x]];i++) if(preb[i]<x) res++;50           for(int i=l[num[y]];i<=y;i++) if(preb[i]<x) res++;51           for(int i=num[x]+1;i<num[y];i++) res+=lower_bound(pre+l[i],pre+r[i]+1,x)-(pre+l[i]);52       }53     P(res);54 }55 inline void update()56 {57     int t=0;58     for(int i=x+1;i<=n;i++)59       if(a[i]==y)60         {*lower_bound(pre+l[num[i]],pre+r[num[i]],preb[i])=x; preb[i]=x;61         sort(pre+l[num[i]],pre+r[num[i]]+1); break;}62     a[0]=y;63     for(int i=x-1;i>=0;i--)64       if(a[i]==y)65         {*lower_bound(pre+l[num[x]],pre+r[num[x]],preb[x])=i; preb[x]=i;66         sort(pre+l[num[x]],pre+r[num[x]]+1); break;}67     int t2=a[x]; a[x]=y;68     for(int i=x;i>=1;i--)69       if(a[i]==t2)70         {t=i; break;}71     for(int i=x+1;i<=n;i++)72       if(a[i]==t2)73         {*lower_bound(pre+l[num[i]],pre+r[num[i]],preb[i])=t; preb[i]=t;74         sort(pre+l[num[i]],pre+r[num[i]]+1); break;}75 }char op[1];76 int main()77 {78     n=G();m=G();79     for(int i=1;i<=n;i++) a[i]=G();80     makeblock(); makepre();81     for(int i=1;i<=m;i++)82       {83         scanf("%s",op);x=G();y=G();84           if(op[0]==‘Q‘) query();85           else update();86       }87     return 0;88 }