墨墨购买了一套N支彩色画笔（其中有些颜色可能相同），摆成一排，你需要回答墨墨的提问。墨墨会向你发布如下指令：
1、 \(Q\) \(L\) \(R\)
代表询问你从第L支画笔到第R支画笔*有几种不同颜色的画笔。
2、 \(R\) \(P\) \(Col\)
把第P支画笔替换为颜色\(Col\)。
为了满足墨墨的要求，你知道你需要干什么了吗？
这道题目跟小Z的袜子非常相像，只是多了一个操作——修改。
我们仍然继续小Z的袜子的想法，如果当前询问的区间之前有修改，那么我们就暴力修改，如果没有，我们就不修改。
这样仍然会出现问题：
有可能在当前询问时，一些由于排序所以先被修改的量此时仍然被修改，但是当前询问时该元素并没有被修改
所以，我们考虑维护一个时间轴，原理跟区间的\([l,r]\)扩张差不多。
设上一个询问时间为\(tim\)
如果当前询问比\(tim\)时间早，那么时光倒流，撤销相应修改
如果当前询问比\(tim\)时间晚，那么时光快进，完成相应修改
于是，这道题目就这样愉快的解决了
最后，送给大家一首打油诗
假如 你被卡了常
不要灰心
忧郁的日子里要心平气和
相信吧
改一改块的长度
就可以快10倍
贴代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=5e4+10;
const int col=1e6+10;
int n,m,len;
int a[maxn];
int cnt1,b[maxn];
struct query{
int l,r,id,tim;
friend bool operator <(query x,query y)
{
if(b[x.l]!=b[y.l])
return x.l<y.l;
if(b[x.r]!=b[y.r])
{
if(b[x.l]&1) return x.r<y.r;
else return x.r>y.r;
}
}
}q[maxn];
struct update{
int x,y;
}upd[maxn];
int cnt2;
int ans[maxn];
int cnt[col];
int now;
void add(int x){now+=!cnt[x]++;}
void del(int x){now-=!--cnt[x];}
int l=0,r=0,tag=0;
void change(int x)
{
if(l<=upd[x].x&&upd[x].x<=r)
{
del(a[upd[x].x]);
add(upd[x].y);
}
swap(upd[x].y,a[upd[x].x]);
}
int main()
{
scanf("%d%d",&n,&m);
len=sqrt(n)*15;
for(int i=1;i<=n;++i)
scanf("%d",&a[i]);
char opt[5];
int x,y;
for(int i=1;i<=m;++i)
{
scanf("%s%d%d",opt,&x,&y);
if(opt[0]=='Q')
++cnt1,q[cnt1]={x,y,cnt1,cnt2};
else
++cnt2,upd[cnt2]={x,y};
b[i]=(i-1)/len+1;
}
stable_sort(q+1,q+cnt1+1);
for(int i=1;i<=cnt1;++i)
{
while(l<q[i].l) del(a[l++]);
while(l>q[i].l) add(a[--l]);
while(r>q[i].r) del(a[r--]);
while(r<q[i].r) add(a[++r]);
while(tag<q[i].tim) change(++tag);
while(tag>q[i].tim) change(tag--);
ans[q[i].id]=now;
}
for(int i=1;i<=cnt1;++i)
printf("%d\n",ans[i]);
return 0;
}