分块，在每个点记录一下它之前离它最近的相同颜色的位置pre[i]，显然问题转化成了求[l,r]中pre[i]<l的值的个数。

这是分块擅长的，在每个块内记录有序表，查询时对零散的暴力，整块的二分即可。

修改时有点麻烦，设修改a[p]。

可能会对pre[p]产生影响；

可能会对p位置之后的第一个 与a[p]修改前相等的值 的pre 产生影响；

可能会对p位置之后的第一个 与a[p]修改后相等的值 的pre 产生影响。

细节蛮多，调了很久。<---蒟蒻。

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          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
         
          =num[y]) {
   for(int i=x;i<=y;i++) if(preb[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 }