#带修改莫队，分块#jzoj 1942 洛谷 1903 数颜色

本文主要是介绍#带修改莫队，分块#jzoj 1942 洛谷 1903 数颜色，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

Q L R代表询问你从第L支画笔到第R支画笔中共有几种不同颜色的画笔。 R P Col 把第P支画笔替换为颜色Col。需要满足查询

分析

这道题看起来就是要离线的，需要用莫队，但是原莫队不支持修改，那么就弄一弄，当然还要用分块优化，就没有什么了（jzoj卡逐字符输入）

代码

#include <cstdio>
#include <cmath>
#include <algorithm>
struct dif{int whe,nnw,pre;}chg[50001]; int a[50001],ans[50001];
struct qus{int l,r,whe,rk;}q[50001]; int n,m,block,color[1000001];
int in(){int ans=0; char c=getchar();while (c<48||c>57) c=getchar();while (c>47&&c<58) ans=ans*10+c-48,c=getchar();return ans;
}
void print(int ans){if (ans>9) print(ans/10); putchar(ans%10+48);}
bool cmp(const qus &a,const qus &b){if (a.l/block!=b.l/block) return a.l/block<b.l/block;//分块if (a.r/block!=b.r/block) return a.r/block<b.r/block;return a.whe<b.whe;
}
int main(){n=in(); m=in(); int tot1=0,tot2=0,l=1,r=0,Ans=0,now=0;for (register int i=1;i<=n;i++) a[i]=in();for (register int i=1;i<=m;i++){char c=getchar();while (c<65||c>90) c=getchar();if (c=='R'){chg[++tot1]=(dif){in(),in(),0};chg[tot1].pre=a[chg[tot1].whe];//前一个答案a[chg[tot1].whe]=chg[tot1].nnw;//现在的答案}else q[++tot2]=(qus){in(),in(),tot1,tot2};}block=ceil(exp((log(tot1)+log(tot2))/3));//jzojREfor (register int i=tot1;i>=1;i--) a[chg[i].whe]=chg[i].pre;std::sort(q+1,q+1+tot2,cmp);for (register int i=1;i<=tot2;i++){while (q[i].l<l) Ans+=!color[a[--l]]++;//原莫队模板while (q[i].l>l) Ans-=!--color[a[l++]];while (q[i].r>r) Ans+=!color[a[++r]]++;while (q[i].r<r) Ans-=!--color[a[r--]];while (q[i].whe<now){int k=chg[now].whe;if (l<=k&&k<=r) Ans-=!--color[a[k]];a[k]=chg[now--].pre;//修改if (l<=k&&k<=r) Ans+=!color[a[k]]++;}while (q[i].whe>now){int k=chg[++now].whe;if (l<=k&&k<=r) Ans-=!--color[a[k]];a[k]=chg[now].nnw;if (l<=k&&k<=r) Ans+=!color[a[k]]++;}ans[q[i].rk]=Ans;//离线返回}for (register int i=1;i<=tot2;i++) print(ans[i]),putchar('\n');return 0;
}