题目大意

有$n$支彩色画笔（颜色可能相同）排成一排，有$m$次操作

1. 询问在$[l,r]$中共有几种颜色不同的画笔

2. 把其中一只画笔替换为别的颜色的画笔

数据范围

$n\leqslant 10000,m\leqslant 10000$

所有画笔的颜色表示为$1\leqslant c[i]\leqslant 10^6$

题解

用$pre[i]$表示在$i$左边最近的相同颜色的画笔的位置，那么问题就转化为求在区间$[l,r]$中，$pre[i]\leq l$的个数

然后修改用暴力重构，询问用分块解决，小部分暴力搜，块整体用二分即可

程序

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define inf 0x3f3f3f3f
using namespace std;
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-48;ch=getchar();}
    return x*f;
}

int n,m,size,tot;
int c[10050],belong[10050],pre[10050],spre[10050],last[1000050];
int l[200],r[200];

inline void init(){
    n=read(),m=read();
    For(i,1,n) c[i]=read();
    size=(int)sqrt(n);
    tot=n%size?n/size+1:n/size;
    For(i,1,tot) l[i]=(i-1)*size+1,r[i]=min(i*size,n);
}
inline void reset(int x){
    For(i,l[x],r[x]) spre[i]=pre[i];
    sort(spre+l[x],spre+r[x]+1);
}
inline int find(int x,int y){
    int ll=l[x],rr=r[x];
    while(ll<=rr){
        int mid=(ll+rr)>>1;
        if (spre[mid]<y) ll=mid+1;
        else rr=mid-1;
    }
    return ll-l[x];
}

inline void build(){
    For(i,1,n){
        pre[i]=last[c[i]];
        last[c[i]]=i;
        belong[i]=(i-1)/size+1;
    }
    For(i,1,tot) reset(i); 
}
inline void change(int x,int y){
    For(i,1,n) last[c[i]]=0;
    c[x]=y;
    For(i,1,n){
        int temp=pre[i];
        pre[i]=last[c[i]];
        if (temp!=pre[i]) reset(belong[i]);
        last[c[i]]=i;
    }
}
inline int query(int x,int y){
    int ans=0;
    if (belong[x]==belong[y]){
        For(i,x,y) if (pre[i]<x) ans++;
        return ans;
    }
    For(i,x,r[belong[x]]) if (pre[i]<x) ans++;
    For(i,l[belong[y]],y) if (pre[i]<x) ans++;
    For(i,belong[x]+1,belong[y]-1) ans+=find(i,x);
    return ans;
}
int main(){
    init();
    build();
    For(i,1,m){
        char ch[5];scanf("%s",ch+1);
        int x=read(),y=read();
        if (ch[1]=='Q') printf("%d\n",query(x,y));
        else change(x,y);
    }
    return 0;
}