带修莫队首先是建立在莫队的基础上的,加入了修改,这时就需要在每个区间中加一个元素——时间,即本次查询前经历了多少次修改,再在莫队中每次查询都将修改时间改到本次(就是将修改不够的按时间增加修改,修改多了的按时间将修改恢复),这样就非常简单,于是我在写洛谷P1903 [国家集训队] 数颜色 / 维护队列时就是这样做的,然后就T了,那是因为这里遗漏了最重要的一点,莫队的速度是因为它的排序方式,要是如果将时间也加入到这种排序方式中,那么就能使它变快,接下来是真正的带修莫队的排序方式:首先将整个数组分块,但是要将它以三次根的方式分块(因为这里的排序是有三个元素的),再是排序,先将区间左端点放入块中,按所在块前后进行排序,在同一个块中的,再讲右端点放入块中,按所在块前后进行排序,又在同一个块中的,根据时间先后排序。
下面来看一道题:
洛谷P1903 [国家集训队] 数颜色 / 维护队列
题目描述
墨墨购买了一套 N 支彩色画笔(其中有些颜色可能相同),摆成一排,你需要回答墨墨的提问。墨墨会向你发布如下指令:
-
Q L R 代表询问你从第 L 支画笔到第 R 支画笔*有几种不同颜色的画笔。
-
R P Col 把第 P 支画笔替换为颜色 Col。
为了满足墨墨的要求,你知道你需要干什么了吗?
输入格式
第 1 行两个整数 N,M,分别代表初始画笔的数量以及墨墨会做的事情的个数。
第 2 行 N 个整数,分别代表初始画笔排中第 i 支画笔的颜色。
第 3 行到第 2+M 行,每行分别代表墨墨会做的一件事情,格式见题*分。
输出格式
对于每一个 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说明/提示
对于30%的数据,n,m≤10000
对于60%的数据,n,m≤50000
对于所有数据,n,m≤133333
所有的输入数据中出现的所有整数均大于等于 1 且不超过 10^6。
这就是一道正常的带修莫队题,其中计算颜色种数的方式就是在缩短区间时,若将某种颜色减到0,那么就将颜色种数-1,在扩大区间时,若某种颜色从无到有,那么就将颜色种数+1。
下面是代码:
#include<iostream> #include<cmath> #include<algorithm> #include<cstring> using namespace std; int n,m,ge,cnt=0,duan=0; int c[133343],tot[1000010],ans[133343]; struct node{ int l,r; int id; int xg; }quyu[133343]; struct nod{ int p; int col; int yuan; }xugai[133343]; bool cmp(node x,node y){ int qx=x.l/ge,qy=y.l/ge; int wx=x.r/ge,wy=y.r/ge; return qx==qy?(wx==wy?x.xg>y.xg:wx<wy):qx<qy; } void add(int x){ tot[c[x]]++; if(tot[c[x]]==1)cnt++; } void del(int x){ tot[c[x]]--; if(tot[c[x]]==0)cnt--; } int main(){ char a; char u; cin>>n>>m; ge=pow(n,0.666); for(int i=1;i<=n;i++){ cin>>c[i]; } for(int i=1;i<=m;i++){ cin>>a; if(a=='R'){ duan++; cin>>xugai[duan].p>>xugai[duan].col; xugai[duan].yuan=c[xugai[duan].p]; c[xugai[duan].p]=xugai[duan].col; } else{ cin>>quyu[i-duan].l>>quyu[i-duan].r; quyu[i-duan].id=i-duan; quyu[i-duan].xg=duan; } } sort(quyu+1,quyu+m+1,cmp); int lasl=1,lasr=1; tot[c[1]]=1; cnt=1; int w=duan; for(int i=1;i<=m;i++){ int rr=quyu[i].r,ll=quyu[i].l; while(lasr<rr)add(++lasr); while(lasl>ll)add(--lasl); while(lasr>rr)del(lasr--); while(lasl<ll)del(lasl++); while(quyu[i].xg>w){ w++; if(xugai[w].p>=lasl&&xugai[w].p<=lasr){ tot[c[xugai[w].p]]--; if(tot[c[xugai[w].p]]==0){ cnt--; } tot[xugai[w].col]++; if(tot[xugai[w].col]==1){ cnt++; } } c[xugai[w].p]=xugai[w].col; } while(quyu[i].xg<w){ if(xugai[w].p>=lasl&&xugai[w].p<=lasr){ tot[c[xugai[w].p]]--; if(tot[c[xugai[w].p]]==0){ cnt--; } tot[xugai[w].yuan]++; if(tot[xugai[w].yuan]==1){ cnt++; } } c[xugai[w].p]=xugai[w].yuan; w--; } ans[quyu[i].id]=cnt; } for(int i=1;i<=m-duan;i++){ printf("%d\n",ans[i]); } return 0; }