题意：给你一列画笔以及他们的颜色，然后有一些修改和询问，修改时单点修改，询问你一段区间中有多少种颜色
思路：如果没有修改的话，就是一个求区间有多少种不同的颜色的一个经典问题，可以用莫队或者主席树来做，带上修改的话，莫队也能做，在我们每次维护的时候要加上一个时间戳，假设当前是3点，而我们处理的问题是2点，我们就会回滚到2点，吧中间的修改操作进行复原，如果是4点，我们就继续处理到4点（看了胡小兔爷的代码，跟着胡小兔爷学个各种东西，莫队传送门）
手（chao）写（xi）代码：
#include <bits/stdc++.h> using namespace std; typedef long long LL; LL read() { LL 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-‘0‘;ch=getchar();} return x*f; } const int maxn=10005,maxe=1000005; int n,m,pl=1,pr=0,cur,res,ans[maxn],a[maxn],cnt[maxe]; int idxC,idxQ,tim[maxn],pos[maxn],val[maxn],pre[maxn]; int num[maxn],block; struct query { int id,tim,l,r; bool operator <(const query &b)const { if(num[l]!=num[b.l])return l<b.l; if(num[r]!=num[b.r])return r<b.r; return id<b.id; } }q[maxn]; void change_add(int cur) { if(pl<=pos[cur]&&pos[cur]<=pr){ cnt[a[pos[cur]]]--; if(!cnt[a[pos[cur]]])res--; } pre[cur]=a[pos[cur]]; a[pos[cur]]=val[cur]; if(pl<=pos[cur]&&pos[cur]<=pr){ if(!cnt[a[pos[cur]]])res++; cnt[a[pos[cur]]]++; } } void change_del(int cur) { if(pl<=pos[cur]&&pos[cur]<=pr){ cnt[a[pos[cur]]]--; if(!cnt[a[pos[cur]]])res--; } a[pos[cur]]=pre[cur]; if(pl<=pos[cur]&&pos[cur]<=pr){ if(!cnt[a[pos[cur]]])res++; cnt[a[pos[cur]]]++; } } void change(int now) { while(cur<idxC&&tim[cur+1]<=now)change_add(++cur); while(cur&&tim[cur]>now)change_del(cur--); } void add(int p) { if(!cnt[a[p]])res++; cnt[a[p]]++; } void del(int p) { cnt[a[p]]--; if(!cnt[a[p]])res--; } int main() { n=read();m=read();block=464; for(int i=1;i<=n;i++)a[i]=read(); for(int i=1;i<=n;i++)num[i]=(i-1)/block+1; for(int i=1;i<=m;i++){ char op[5]; scanf("%s",op); if(op[0]==‘Q‘){ idxQ++; q[idxQ].id=idxQ;q[idxQ].tim=i; q[idxQ].l=read();q[idxQ].r=read(); } else{ tim[++idxC]=i; pos[idxC]=read(); val[idxC]=read(); } } sort(q+1,q+1+idxQ); for(int i=1;i<=idxQ;i++){ change(q[i].tim); while(pl>q[i].l)add(--pl); while(pr<q[i].r)add(++pr); while(pl<q[i].l)del(pl++); while(pr>q[i].r)del(pr--); ans[q[i].id]=res; } for(int i=1;i<=idxQ;i++){ printf("%d\n",ans[i]); } return 0; }
原文：https://www.cnblogs.com/lalalatianlalu/p/9456658.html