今天的内容是带修莫队。
例题：P1903 [国家集训队]数颜色 / 维护队列
题目描述
墨墨购买了一套N支彩色画笔（其中有些颜色可能相同），摆成一排，你需要回答墨墨的提问。墨墨会向你发布如下指令：
1、 Q L R代表询问你从第L支画笔到第R支画笔中共有几种不同颜色的画笔。
2、 R P Col 把第P支画笔替换为颜色Col。
为了满足墨墨的要求，你知道你需要干什么了吗？
输入格式
输出格式
对于每一个Query的询问，你需要在对应的行中给出一个数字，代表第L支画笔到第R支画笔中共有几种不同颜色的画笔。
输入输出样例
输入 #1
- 6 5
- 1 2 3 4 5 5
- Q 1 4
- Q 2 6
- R 1 2
- Q 1 4
- Q 2 6
输出 #1
- 4
- 4
- 3
- 4
说明/提示
对于100%的数据，N≤50000，M≤50000，所有的输入数据中出现的所有整数均大于等于1且不超过10^6。
本题可能轻微卡常数
来源：bzoj2120
本题数据为洛谷自造数据，使用CYaRon耗时5分钟完成数据制作。
带修莫队
莫队是一种很神奇的离线算法。可以解决区间上的问题，通过排序和对询问分块来优化暴力。
普通的莫队题目都是给定的序列，不断的询问。
那么如果在询问中夹杂了一些修改操作，莫队还能做吗？
答案当然是可以的。
回顾一下莫队的实现方法：
1.提前预处理
2.询问分块排序
3.双指针移动求解。
唯一会因为修改而产生变化的操作就是3操作。
可以发现：当出现了修改操作之后，我当前询问处理的区间可能就不是我们本来要找的区间了。
那么怎么办呢？
借鉴一下可持久化线段树的思想：时光回溯。
我们可以先把带修莫队当做一般的莫队来做，做完之后如果发现时间对不上就时光倒流。
准确的说是：考虑两个时间点的操作之间的代价。
这么说来，只要在普通莫队的一堆 while 循环后面再加两个就OK。
- while(now<q[i].t)
- change(++now);
- while(now>q[i].t)
- change(now--);
代码
- #include<iostream>
- #include<cstdio>
- #include<cstring>
- #include<algorithm>
- #include<cmath>
- using namespace std;
- const int N=50005;
- int col[N],n,m,sum[1000005],be[N];
- int fans,qnum,cnum,ans[N];
- struct qs{
- int l,r,t,id;
- }q[N];
- struct cs{
- int x,i;
- }c[N];
- bool cmp(qs x,qs y) {
- if(be[x.l]!=be[y.l])
- return x.l<y.l;
- if(be[x.r]!=be[y.r])
- return x.r<y.r;
- return x.t<y.t;
- }
- void upd1(int x) {
- if(!sum[col[x]])
- ++fans;
- ++sum[col[x]];
- return;
- }
- void upd2(int x) {
- --sum[col[x]];
- if(!sum[col[x]])
- --fans;
- return;
- }
- int l,now;
- void change(int x) {
- if(c[x].i<=r&&c[x].i>=l) {
- --sum[col[c[x].i]];
- if(!sum[col[c[x].i]])
- --fans;
- if(!sum[c[x].x])
- ++fans;
- ++sum[c[x].x];
- }
- swap(c[x].x,col[c[x].i]);
- return;
- }
- int main()
- {
- cin>>n>>m;
- int xx=pow(n,2.0/3.0);
- char opt;
- for(int i=1;i<=n;i++) {
- cin>>col[i];
- be[i]=i/xx+1;
- }
- for(int i=1;i<=m;i++) {
- cin>>opt;
- if(opt==‘Q‘) {
- ++qnum;
- cin>>q[qnum].l>>q[qnum].r;
- q[qnum].t=cnum;
- q[qnum].id=qnum;
- }
- else {
- ++cnum;
- cin>>c[cnum].i>>c[cnum].x;
- }
- }
- sort(q+1,q+qnum+1,cmp);
- l=r=fans=now=0;
- for(int i=1;i<=qnum;i++) {
- while(l<q[i].l)
- upd2(l++);
- while(l>q[i].l)
- upd1(--l);
- while(r>q[i].r)
- upd2(r--);
- while(r<q[i].r)
- upd1(++r);
- while(now<q[i].t)
- change(++now);
- while(now>q[i].t)
- change(now--);
- ans[q[i].id]=fans;
- }
- for(int i=1;i<=qnum;i++)
- cout<<ans[i]<<endl;
- return 0;
- }
