思路by lyd,ych

我们参考选择客栈的思路，设pre[i]是i前面一个和i颜色相同的画笔，col[i]记录i的颜色

我们发现，当pre[i]<l<=i<=r时，col[i]第一次出现在区间[l,r]中

我们的问题是区间[l,r]中有多少不同的颜色，也就是统计区间[l,r]中有多少颜色是第一次出现

这样查询就被我们切掉了

然后就是令人崩溃的修改。

我们修改一个点i，需要知道pre[i],满足pre[j]=i的j,以及更改之后pre[i]是多少

我们可以对每一个颜色搞一个set(最多1e6颜色不会爆空间的)。在修改点i的时候，在set里面找到i的后继，令pre[i的后继]=i的前驱，然后把i从原来的set中删掉，更改col[i]。在新的set里面更新pre[i]。

注意：每个set要先插入0,inf以防找到一些神奇的玩意。

正解：带修莫队我不会

不会

差点T飞的代码

#include
     
      using namespace std;inline int read(){    char ch=getchar();    int x=0;bool f=0;    while(ch<'0'||ch>'9')    {        if(ch=='-')f=1;        ch=getchar();    }    while(ch>='0'&&ch<='9')    {        x=(x<<3)+(x<<1)+(ch^48);        ch=getchar();    }    return f?-x:x;}const int inf=214748364;set 
      
        qaq[1000009];set 
       
        ::iterator qwq,www,owo;int n,m,col[500009],pre[500009],lst[500009];int main(){    n=read();    m=read();    for(int i=1;i<=n;i++)     qaq[i].insert(0),qaq[i].insert(inf);    for(int i=1;i<=n;i++)     {         col[i]=read();         pre[i]=lst[col[i]];         lst[col[i]]=i;         qaq[col[i]].insert(i);     }     for(int i=1;i<=m;i++)     {         char cz=getchar();         while(cz!='Q'&&cz!='R')cz=getchar();         int gs1=read(),gs2=read();//搞事1，搞事2         if(cz=='Q')         {             int gs=0;             for(int i=gs1;i<=gs2;i++)               if(pre[i]