http://www.cnblogs.com/autsky-jadek/p/4020296.html
同bzoj2120。
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,sz,sum,l[],r[],num[],pre[],preb[],a[],x,y,pos[];
int Res,Num;char C,CH[];
inline int G()
{
Res=;C='*';
while(C<''||C>'')C=getchar();
while(C>=''&&C<=''){Res=Res*+(C-'');C=getchar();}
return Res;
}
inline void P(int x)
{
Num=;if(!x){putchar('');puts("");return;}
while(x>)CH[++Num]=x%,x/=;
while(Num)putchar(CH[Num--]+);
puts("");
}
void makeblock()
{
sz=sqrt((double)n*log2(n)); if(!sz) sz=;
for(sum=;sum*sz<n;sum++)
{
l[sum]=(sum-)*sz+;
r[sum]=sum*sz;
for(int i=l[sum];i<=r[sum];i++)
num[i]=sum;
}
l[sum]=sz*(sum-)+;
r[sum]=n;
for(int i=l[sum];i<=r[sum];i++)
num[i]=sum;
}
void makepre()
{
for(int i=;i<=n;i++) {pre[i]=pos[a[i]]; pos[a[i]]=i;}
memcpy(preb,pre,sizeof(pre));
for(int i=;i<=sum;i++) sort(pre+l[i],pre+r[i]+);
}
inline void query()
{
int res=;
if(num[x]+>=num[y]) {for(int i=x;i<=y;i++) if(preb[i]<x) res++;}
else
{
for(int i=x;i<=r[num[x]];i++) if(preb[i]<x) res++;
for(int i=l[num[y]];i<=y;i++) if(preb[i]<x) res++;
for(int i=num[x]+;i<num[y];i++) res+=lower_bound(pre+l[i],pre+r[i]+,x)-(pre+l[i]);
}
P(res);
}
inline void update()
{
int t=;
for(int i=x+;i<=n;i++)
if(a[i]==y)
{*lower_bound(pre+l[num[i]],pre+r[num[i]],preb[i])=x; preb[i]=x;
sort(pre+l[num[i]],pre+r[num[i]]+); break;}
a[]=y;
for(int i=x-;i>=;i--)
if(a[i]==y)
{*lower_bound(pre+l[num[x]],pre+r[num[x]],preb[x])=i; preb[x]=i;
sort(pre+l[num[x]],pre+r[num[x]]+); break;}
int t2=a[x]; a[x]=y;
for(int i=x;i>=;i--)
if(a[i]==t2)
{t=i; break;}
for(int i=x+;i<=n;i++)
if(a[i]==t2)
{*lower_bound(pre+l[num[i]],pre+r[num[i]],preb[i])=t; preb[i]=t;
sort(pre+l[num[i]],pre+r[num[i]]+); break;}
}char op[];
int main()
{
n=G();m=G();
for(int i=;i<=n;i++) a[i]=G();
makeblock(); makepre();
for(int i=;i<=m;i++)
{
scanf("%s",op);x=G();y=G();
if(op[]=='Q') query();
else update();
}
return ;
}