简介
莫队算法是由莫涛提出的算法。在莫涛提出莫队算法之前,莫队算法已经在 Codeforces 的高手圈里小范围流传,但是莫涛是第一个对莫队算法进行详细归纳总结的人。莫涛提出莫队算法时,只分析了普通莫队算法,但是经过 OIer 和 ACMer 的集体智慧改造,莫队有了多种扩展版本。
莫队算法可以解决一类离线区间询问问题,适用性极为广泛。同时将其加以扩展,便能轻松处理树上路径询问以及支持修改操作。
— OI wiki
普通莫队
引例:区间不同数
Description
有一个长度为 $n$ 的序列,有 $m$ 次询问,每次询问某个区间内出现过的数值种类数。
$1\leq n \leq 5\times 10^4,1\leq m \leq 2\times 10^5,0\leq a_i \leq 10^6$
Solution
首先考虑暴力,如果对于每一个询问,直接暴力枚举区间每个数,开个桶统计每个数字是否出现过,显然这种做法会超时,复杂度为 $O(NM)$。
这时候就要用到莫队算法了。
那么莫队是什么呢?
其实就是优雅的暴力。
我们现在可以思考一个问题,如果你已经得知区间 $[l,r]$ 的答案,那么如何求区间 $[l,r+1]$ 的答案呢?
显然区间 $[l,r+1]$ 只比 $[l,r]$ 多了元素 $a[r]$,那么我们只需要判断 $a[r]$ 对答案是否有贡献即可。
那么什么时候 $a[r]$ 对答案有贡献呢?
显然只有当区间 $[l,r]$ 中 $a[r]$ 的出现次数为 $0$。
那么事情就很好办了,我们只需要开一个 $cnt$ 数组统计每个数字目前出现的次数,每次对答案造成贡献的条件是 $cnt[a[r]]==0$。
同理,我们如果知道了区间 $[l,r]$ 的答案,我们就可以知道 $[l-1,r],[l+1,r],[l,r-1]$ 的答案。
而且这个复杂度是 $O(1)$ 的,那么处理下一个询问的复杂度就是 $O(|r_i-r_{i-1}|+|l_i-l_{i-1}|)$ 的。
这样的复杂度在随机数据中表现很好,但是毒瘤的出题人也不难卡你。
那么此时就需要莫队优化的精髓来减小复杂度了。
我们考虑进行分块,不妨设块大小为 $\sqrt{N}$,把每个点分入一个块内,然后将所有询问按照左端点所在块为第一关键字排序,右端点的序号为第二关键字排序。
下面我们来解释下为什么要这么做:
- 所在块相同时,右端点递增是 $O(N)$ 的,块共有个 $O(\sqrt{N})$,复杂度为 $O(N^{1.5})$
- 分块转移时,右端点最多变化 $N$,块共有 $O(\sqrt{N})$ 个,复杂度为 $O(N^{1.5})$
- 块相同时,左端点最多变化 $\sqrt{N}$,块转移时,左端点最多变化 $2\sqrt{N}$,共有 $N$ 个询问,复杂度为 $O(N^{1.5})$
所以总时间复杂度为 $O(N^{1.5})$。
Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
#include<bits/stdc++.h> #define Tp template<typename Ty> #define Ts template<typename Ty,typename... Ar> #define W while #define I inline #define RI register int #define LL long long #define Cn const #define CI Cn int& #define gc getchar #define D isdigit(c=gc()) #define pc(c) putchar((c)) #define min(x,y) ((x)<(y)?(x):(y)) #define max(x,y) ((x)>(y)?(x):(y)) using namespace std; namespace Debug{ Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;} Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);} Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;} #define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__) }using namespace Debug; namespace FastIO{ Tp I void read(Ty& x){char c;int f=1;x=0;W(!D) f=c^'-'?1:-1;W(x=(x<<3)+(x<<1)+(c&15),D);x*=f;} Ts I void read(Ty& x,Ar&... y){read(x),read(y...);} Tp I void write(Ty x){x<0&&(pc('-'),x=-x,0),x<10?(pc(x+'0'),0):(write(x/10),pc(x%10+'0'),0);} Tp I void writeln(Cn Ty& x){write(x),pc('\n');} }using namespace FastIO; Cn int N=5e4+10,M=2e5+10,C=1e6+10; int n,m,S,a[N],bl[N],cnt[C],Ans,ans[M],tot,l,r; struct Que{int l,r,id;}q[M]; I bool cmp(Cn Que& x,Cn Que& y){return bl[x.l]^bl[y.l]?x.r<y.r:x.l<y.l;} int main(){ RI i;for(read(n),S=sqrt(n),i=1;i<=n;i++) read(a[i]);for(read(m),i=1;i<=m;i++) read(q[i].l,q[i].r),q[i].id=i; for(i=1;i<=n;i++) if(!((i-1)%S)) bl[i]=++tot;else bl[i]=tot;for(sort(q+1,q+m+1,cmp),l=1,r=0,i=1;i<=m;i++){ W(l<q[i].l) !(--cnt[a[l++]])&&Ans--; W(l>q[i].l) !(cnt[a[--l]]++)&&Ans++; W(r<q[i].r) !(cnt[a[++r]]++)&&Ans++; W(r>q[i].r) !(--cnt[a[r--]])&&Ans--; ans[q[i].id]=Ans; }for(i=1;i<=m;i++) writeln(ans[i]);return 0; } |
莫队的劣处
不难发现,莫队只支持离线区间询问,对于在线问题,我们并不能采用莫队来解决。
并且使用莫队需要一些卡常技巧,才能战胜出题人。
带修莫队
一般的莫队是不支持修改的,但是如果我们稍微修改一下,就可以让莫队资瓷修改啦~
就像 DP 一样,可以强行加上一维时间维, 表示这次操作的时间。
时间维表示经历的修改次数。
即把询问 $[l,r]$ 变成 $[l,r,time]$。
那么我们的坐标也可以在时间维上移动,即 $[l,r,time]$ 多了一维可以移动的方向。
这样的转移也是 $O(1)$ 的,但是我们排序又多了一个关键字,再搞搞就行了。
可以用和普通莫队类似的方法排序转移,做到 $O(N^{\frac{5}{3}})$。
这一次我们排序的方式是以 $N^{\frac{2}{3}}$ 为一块,分成了 $N^{\frac{1}{3}}$ 块,第一关键字是左端点所在块,第二关键字是右端点所在块,第三关键字是时间。
还是来证明一下时间复杂度:
- 左右端点所在块不变,时间在排序后单调向右移,这样的复杂度是 $O(N)$;
- 若左右端点所在块改变,时间一次最多会移动 $N$ 个格子,时间复杂度 $O(N)$;
- 左端点所在块一共有 $N^{\frac{1}{3}}$ 中,右端点也是 $N^{\frac{1}{3}}$ 种,一共 $N^{\frac{1}{3}}$ 种,每种乘上移动的复杂度 $O(N)$,总复杂度 $O(N^{\frac{5}{3}})$。
例题:LuoguP1903 [国家集训队]数颜色 / 维护队列
Description
有一个长度为 $n$ 的序列,要支持 $m$ 次询问或修改。
题目需要你进行的操作有:
Q l r
表示询问 $[l,r]$ 中出现过的数值种类数。R p col
表示把第 $p$ 个数替换成颜色 $col$。
Solution
带修莫队模板
Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
#include<bits/stdc++.h> #define Tp template<typename Ty> #define Ts template<typename Ty,typename... Ar> #define W while #define I inline #define RI register int #define LL long long #define Cn const #define CI Cn int& #define gc getchar #define D isdigit(c=gc()) #define pc(c) putchar((c)) #define min(x,y) ((x)<(y)?(x):(y)) #define max(x,y) ((x)>(y)?(x):(y)) using namespace std; namespace Debug{ Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;} Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);} Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;} #define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__) }using namespace Debug; namespace FastIO{ Tp I void read(Ty& x){char c;int f=1;x=0;W(!D) f=c^'-'?1:-1;W(x=(x<<3)+(x<<1)+(c&15),D);x*=f;} Ts I void read(Ty& x,Ar&... y){read(x),read(y...);} Tp I void write(Ty x){x<0&&(pc('-'),x=-x,0),x<10?(pc(x+'0'),0):(write(x/10),pc(x%10+'0'),0);} Tp I void writeln(Cn Ty& x){write(x),pc('\n');} }using namespace FastIO; Cn int N=1e4+10,M=1e6+10; int n,m,S,a[N],l,r,t,cnt[M],bl[N],tot,Ans,ans[N],cntp,cntq,lst[M]; struct Que{int l,r,lst,t;}p[N],q[N]; I int RC(){char c=gc();W(c^'Q'&&c^'R') c=gc();return c^'Q';} I bool cmp(Cn Que& x,Cn Que& y){return bl[x.l]^bl[y.l]?x.l<y.l:bl[x.r]^bl[y.r]?x.r<y.r:x.t<y.t;} I void Upd(CI x,CI col){l<=p[x].l&&p[x].l<=r&&(!(--cnt[a[p[x].l]])&&Ans--,!(cnt[col]++)&&Ans++),a[p[x].l]=col;} int main(){ RI i;for(read(n,m),i=1;i<=n;i++) read(a[i]),lst[i]=a[i];for(i=1;i<=m;i++) RC()?(p[++cntp].t=cntq,read(p[cntp].l,p[cntp].r),p[cntp].lst=lst[p[cntp].l],lst[p[cntp].l]=p[cntp].r,0) :(q[++cntq].t=cntp,read(q[cntq].l,q[cntq].r),q[cntq].lst=cntq,0); for(S=pow(n,2.0/3),i=1;i<=n;i++) bl[i]=!((i-1)%S)?++tot:tot;for(sort(q+1,q+cntq+1,cmp),t=-1,r=0,l=i=1;i<=cntq;i++){ W(t<q[i].t) ++t,Upd(t,p[t].r);W(t>q[i].t) Upd(t,p[t].lst),t--; W(l<q[i].l) !(--cnt[a[l++]])&&Ans--;W(l>q[i].l) !(cnt[a[--l]]++)&&Ans++; W(r<q[i].r) !(cnt[a[++r]]++)&&Ans++;W(r>q[i].r) !(--cnt[a[r--]])&&Ans--; ans[q[i].lst]=Ans; }for(i=1;i<=cntq;i++) writeln(ans[i]);return 0; } |
树上莫队
直接类似于树分块,直接在 $Dfs$ 时,如果子树大小超过块大小就直接合成一个块即可。
其他操作类似于普通莫队。
显然,如果直接这样操作肯定是不行的。
因为两个端点还是需要计数的。
容易想到,只有 $LCA$ 才可能重复,所以每次不标记 $LCA$,询问答案时再标记,最后撤销即可。
例题:LuoguP4074 [WC2013] 糖果公园
Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
#include<bits/stdc++.h> #define Tp template<typename Ty> #define Ts template<typename Ty,typename... Ar> #define W while #define I inline #define RI register int #define LL long long #define Cn const #define CI Cn int& #define gc getchar //#define D isdigit(c=gc()) //#define pc(c) putchar((c)) //#define min(x,y) ((x)<(y)?(x):(y)) //#define max(x,y) ((x)>(y)?(x):(y)) using namespace std; namespace Debug{ Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;} Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);} Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;} #define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__) }using namespace Debug; namespace FastIO{ #define FS 100000 #define tc() (FA==FB&&(FB=(FA=FI)+fread(FI,1,FS,stdin),FA==FB)?EOF:*FA++) #define pc(c) (FC==FE&&(clear(),0),*FC++=c) int T;char c,FI[FS],FO[FS],OS[FS],*FA=FI,*FB=FI,*FC=FO,*FE=FO+FS; I void clear() {fwrite(FO,1,FC-FO,stdout),FC=FO;} Tp I void read(Ty& x) {x=0;W(!isdigit(c=tc()));W(x=(x<<3)+(x<<1)+(c&15),isdigit(c=tc()));} Ts I void read(Ty& x,Ar&... y) {read(x),read(y...);} Tp I void writeln(Ty x) {W(OS[++T]=x%10+48,x/=10);W(T) pc(OS[T--]);pc('\n');} }using namespace FastIO; Cn int N=1e6+10; int n,m,q,S,a[N],w[N],col[N],lst[N],fir[N],nxt[N<<1],son[N<<1],tot,cnt,cts,dep[N],dfn[N],bl[N],stk[N],tp,f[N],cnte,cntp,t,vis[N],tim[N],lca,mx[N],top[N],sz[N]; LL Ans,ans[N]; struct Edit{int lst,x,y;}e[N]; struct Que{int l,r,t,id;}p[N]; I bool cmp(Cn Que& x,Cn Que& y){return bl[x.l]^bl[y.l]?bl[x.l]<bl[y.l]:bl[x.r]^bl[y.r]?bl[x.r]<bl[y.r]:x.t<y.t;} I void Add(CI x,CI y){nxt[++tot]=fir[x],fir[x]=tot,son[tot]=y;} #define to son[i] I int Dfs(CI x,CI fa){ RI i,sum=0;for(sz[x]=1,dep[x]=dep[f[x]=fa]+1,dfn[x]=++cnt,i=fir[x];i;i=nxt[i]) if(to^fa&&(sum+=Dfs(to,x),sz[x]+=sz[to],sz[to]>sz[mx[x]]&&(mx[x]=to,0),sum>=S)){ ++cts;W(sum--) bl[stk[tp--]]=cts; }return stk[++tp]=x,sum+1; } I void Dfs2(CI x,CI Top){ RI i;if(top[x]=Top,mx[x]) Dfs2(mx[x],Top); for(i=fir[x];i;i=nxt[i]) to^f[x]&&mx[x]^to&&(Dfs2(to,to),0); } I int Lca(RI x,RI y){ W(top[x]^top[y]) dep[top[x]]<dep[top[y]]&&(swap(x,y),0),x=f[top[x]]; return dep[x]<dep[y]?x:y; } I int PU(RI x){return (vis[x]?Ans-=1LL*w[tim[col[x]]--]*a[col[x]]:Ans+=1LL*w[++tim[col[x]]]*a[col[x]]),vis[x]^=1,0;} I void Upd(CI x,CI v){vis[x]?(PU(x),col[x]=v,PU(x)):col[x]=v;} I void Chg(RI x,RI y){W(x^y) dep[x]<dep[y]&&(swap(x,y),0),PU(x),x=f[x];} int main(){ RI i,j,x,y;for(read(n,m,q),S=pow(n,0.60),i=1;i<=m;i++) read(a[i]);for(i=1;i<=n;i++) read(w[i]);for(i=1;i<n;i++) read(x,y),Add(x,y),Add(y,x); for(i=1;i<=n;i++) read(col[i]),lst[i]=col[i];Dfs(1,0),Dfs2(1,1);if(top){++cts;W(tp) bl[stk[tp--]]=cts;}for(i=1;i<=q;i++) if(read(j,x,y),!j) e[++cnte]=(Edit){lst[x],x,y},lst[x]=y;else dfn[x]>dfn[y]&&(swap(x,y),0),p[++cntp]=(Que){x,y,cnte,cntp}; for(sort(p+1,p+cntp+1,cmp),i=1;i<=(t=p[1].t);i++) Upd(e[i].x,e[i].y); for(Chg(p[1].l,p[1].r),PU(lca=Lca(p[1].l,p[1].r)),ans[p[1].id]=Ans,PU(lca),i=2;i<=cntp;i++){ W(t<p[i].t) ++t,Upd(e[t].x,e[t].y);W(t>p[i].t) Upd(e[t].x,e[t].lst),t--; Chg(p[i-1].l,p[i].l),Chg(p[i-1].r,p[i].r),PU(lca=Lca(p[i].l,p[i].r)),ans[p[i].id]=Ans,PU(lca); }for(i=1;i<=cntp;i++) writeln(ans[i]);return clear(),0; } |
回滚莫队
例题:AT1219 歴史の研究
Solution
回滚莫队类似于普通莫队进行排序。
查询直接枚举每一个块,而该块所有右端点都是单调递增的,而左端点都在同一个块内移动,从而计算每个询问的值。
每次到下个块的左端点直接全部清空即可。
Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
#include<bits/stdc++.h> #define Tp template<typename Ty> #define Ts template<typename Ty,typename... Ar> #define W while #define I inline #define RI register int #define LL long long #define Cn const #define CI Cn int& #define gc getchar #define D isdigit(c=gc()) #define pc(c) putchar((c)) using namespace std; namespace Debug{ Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;} Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);} Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;} #define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__) }using namespace Debug; namespace FastIO{ Tp I void read(Ty& x){char c;int f=1;x=0;W(!D) f=c^'-'?1:-1;W(x=(x<<3)+(x<<1)+(c&15),D);x*=f;} Ts I void read(Ty& x,Ar&... y){read(x),read(y...);} Tp I void write(Ty x){x<0&&(pc('-'),x=-x,0),x<10?(pc(x+'0'),0):(write(x/10),pc(x%10+'0'),0);} Tp I void writeln(Cn Ty& x){write(x),pc('\n');} }using namespace FastIO; Cn int N=1e5+10; int n,m,sz,bl[N],tot,cnt[N],lsh[N],a[N]; LL Ans,ans[N],lst=0; struct Que{int l,r,id;}q[N]; I bool cmp(Cn Que& x,Cn Que& y){return bl[x.l]^bl[y.l]?bl[x.l]<bl[y.l]:x.r<y.r;} I void Add(RI x,CI v){cnt[a[x]]+=v,Ans=max(Ans,1LL*cnt[a[x]]*lsh[a[x]]);} int main(){ // freopen("H.in","r",stdin);freopen("H.out","w",stdout); RI i,j,l,r;for(read(n,m),sz=sqrt(n),i=1;i<=n;i++) read(a[i]),lsh[i]=a[i],bl[i]=(i-1)/sz+1;for(i=1;i<=m;i++) read(q[i].l,q[i].r),q[i].id=i; for(sort(lsh+1,lsh+n+1),tot=unique(lsh+1,lsh+n+1)-lsh-1,i=1;i<=n;i++) a[i]=lower_bound(lsh+1,lsh+tot+1,a[i])-lsh; for(sort(q+1,q+m+1,cmp),l=i=1,r=0;i<=m;i++){ if(l=min(n,sz*bl[q[i].l]),bl[q[i].l]^bl[q[i-1].l]) lst=Ans=0,r=l-1,memset(cnt,0,sizeof(cnt));//每次从块的最右端出发 Ans=lst;W(r>q[i].r) Add(r--,-1);W(r<q[i].r) Add(++r,1); lst=Ans;W(l>q[i].l) Add(--l,1);ans[q[i].id]=Ans; for(j=min(n,sz*bl[q[i].l])-1;j>=l;j--) cnt[a[j]]--; }for(i=1;i<=m;i++) writeln(ans[i]);return 0; } |