[文章目录]
Description
墨墨购买了一套N支彩色画笔（其中有些颜色可能相同），摆成一排，你需要回答墨墨的提问。墨墨会像你发布如下指令： 1、 Q L R代表询问你从第L支画笔到第R支画笔中共有几种不同颜色的画笔。 2、 R P Col 把第P支画笔替换为颜色Col。为了满足墨墨的要求，你知道你需要干什么了吗？N≤10000，M≤10000
exm？？？我学了假的带修改莫队？？？
按照正常莫队排序处理询问，记录每个询问前面出现的修改情况，暴力改？？？好吧。。修改次数不超过1000，那么每次都是1000的话时间复杂度也是对的，2333；
本来还是以为三个维度有什么奇怪的排序方法使得轮流操作的曼哈顿距离降低呢？？？
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,w[10010],blo;
int num[1001000],fna[10100];
int cnt,tot;
struct ques
{
int l,r,p,id;
}q[10010];
struct fix
{
int p,u,n;
}f[1100];
inline bool cmp(ques x,ques y) {return x.l/blo==y.l/blo?x.r<y.r:x.l<y.l;}
int l=1,r,tim,ans;
inline void add(int val) {ans+=(!num[val]); num[val]++;}
inline void del(int val) {num[val]--; ans-=(!num[val]);}
int main()
{
scanf("%d%d",&n,&m); blo=sqrt(1.0*n);
for(int i=1;i<=n;++i) scanf("%d",w+i);
char sw[10];
while(m--)
{
scanf("%s",sw);
if(sw[0]=='Q')
{
cnt++; scanf("%d%d",&q[cnt].l,&q[cnt].r);
q[cnt].p=tot; q[cnt].id=cnt;
}
else
{
tot++; scanf("%d%d",&f[tot].p,&f[tot].n);
f[tot].u=w[f[tot].p]; w[f[tot].p]=f[tot].n;
}
}
sort(q+1,q+cnt+1,cmp); tim=tot;
for(int i=1;i<=cnt;++i)
{
while(tim<q[i].p)
{
tim++; w[f[tim].p]=f[tim].n;
if(f[tim].p>=l&&f[tim].p<=r) del(f[tim].u),add(f[tim].n);
}
while(tim>q[i].p)
{
w[f[tim].p]=f[tim].u;
if(f[tim].p>=l&&f[tim].p<=r) del(f[tim].n),add(f[tim].u);
tim--;
}
while(r<q[i].r) add(w[++r]);
while(l>q[i].l) add(w[--l]);
while(r>q[i].r) del(w[r--]);
while(l<q[i].l) del(w[l++]);
fna[q[i].id]=ans;
}
for(int i=1;i<=cnt;++i) printf("%d\n",fna[i]);
return 0;
}