浅谈莫队 – yzxoi

简介

莫队算法是由莫涛提出的算法。在莫涛提出莫队算法之前，莫队算法已经在 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

#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

#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

#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

#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;
}

近期文章

近期评论

文章归档

简介

普通莫队

引例：区间不同数

Description

Solution

Code

莫队的劣处

带修莫队

例题：LuoguP1903 [国家集训队]数颜色 / 维护队列

Description

Solution

Code

树上莫队

例题：LuoguP4074 [WC2013] 糖果公园

Code

回滚莫队

例题：AT1219 歴史の研究

Solution

Code

发送评论编辑评论

简介

普通莫队

引例：区间不同数

Description

Solution

Code

莫队的劣处

带修莫队

例题：LuoguP1903 [国家集训队]数颜色 / 维护队列

Description

Solution

Code

树上莫队

例题：LuoguP4074 [WC2013] 糖果公园

Code

回滚莫队

例题：AT1219 歴史の研究

Solution

Code

发送评论 编辑评论

推荐文章

发送评论编辑评论