莫队算法学习笔记

Published on 2016-12-23

先声明一下,所有代码区间均为左闭右开 [l,r)[l, r),点的下标均从 00 开始。

概述

莫队算法是由莫涛提出的算法,可以解决一类离线区间询问问题,适用性极为广泛。同时将其加以扩展,便能轻松处理树上路径询问以及支持修改操作。

形式

普通莫队

对于序列上的区间询问问题,如果从 [l,r][l, r] 的答案能够 O(1)O(1) 扩展到 [l1,r],[l+1,r],[l,r+1],[l,r1][l - 1, r], [l + 1, r],[l, r + 1],[l, r - 1] 的答案,那么可以在 O(nn)O(n\sqrt n) 的复杂度内求出所有询问的答案。

实现:离线后排序,顺序处理每个询问,暴力从上一个区间的答案转移到下一个区间答案。
排序方法:设定块的长度为 SS,按照 (lS,r)(\lfloor\frac l S\rfloor, r) 二元组从小到大排序。
复杂度分析:设序列长度为 nn,询问个数为 mm。可以发现从 (l1,r1)(l_1, r_1) 转移到 (l2,r2)(l_2, r_2) 的代价为他们之间的曼哈顿距离。对于每一个询问序列中的每一个块(第一关键字相同),整个块内纵坐标最多变化 nn 长度(纵坐标必然单调不减),对于每个询问,横坐标最多变化 SS。一共有 nS\frac n S 个块,相邻块之间转移的复杂度为 O(n)O(n),所以复杂度为 O(n2S+mS+n2S)O(\frac {n^2} S + mS + \frac {n^2} S),不妨让 n,mn, m 同阶,取 S=nS = \sqrt n 时可达到最优复杂度 O(nn)O(n\sqrt n)

模板

int l = 0, r = 0, nowAns = 0;

inline void move(int pos, int sign) {
    // update nowAns
}

void solve() {
    BLOCK_SIZE = int(ceil(pow(n, 0.5)));
      sort(querys, querys + m);
    for (int i = 0; i < m; ++i) {
        const query &q = querys[i];
        while (l > q.l) move(--l, 1);
        while (r < q.r) move(r++, 1);
        while (l < q.l) move(l++, -1);
        while (r > q.r) move(--r, -1);
        ans[q.id] = nowAns;
    }
}

BZOJ 2038

带修改莫队

考虑普通莫队加入修改操作,如果修改操作可以 O(1)O(1) 的应用以及撤销(同时也要维护当前区间的答案),那么可以在 O(n53)O(n^{\frac 5 3}) 的复杂度内求出所有询问的答案。

实现:离线后排序,顺序遍历询问,先将时间转移到当前询问的时间,然后再像普通莫队一样转移区间。
排序方法:设定块的长度为 S1S_1S2S_2,按照 (lS1,rS2,t)(\lfloor\frac l {S_1}\rfloor, \lfloor\frac r {S_2}\rfloor, t) 的三元组小到大排序,其中 tt 表示这个询问的时刻之前经历过了几次修改操作。
复杂度分析:考虑询问序列中的每个小块,小块内每个询问的一二关键字相同。在这个小块内,显然 tt 最多变化 mm,对于每个询问,l,rl, r 最多变化 S1S_1S2S_2,一共有 n2S1S2\frac {n^2} {S_1S_2} 个这样的块,相邻块之间转移的复杂度为 O(n)O(n),总复杂度就是 O(mS1+mS2+n2mS1S2+n2mS1S2)O(mS_1 + mS_2 + \frac {n^2m} {S_1S_2} + \frac {n^2m} {S_1S_2}),不妨设 n,mn, m 同阶,取 S1=S2=n23S_1 = S_2 = n ^ {\frac 2 3} 时可达到最优复杂度 O(n53)O(n^{\frac 5 3})

代码

int l = 0, r = 0, t = 0, nowAns = 0;

inline void move(int pos, int sign) {
    // update nowAns
}

inline void moveTime(int t, int sign) {
    // apply or revoke modification
    // update nowAns
}

void solve() {
    BLOCK_SIZE = int(ceil(pow(n, 2.0 / 3)));
    sort(querys, querys + m);
    for (int i = 0; i < q1; ++i) {
        const query q = querys[i];
        while (t < q.t) moveTime(t++, 1);
        while (t > q.t) moveTime(--t, -1);
        while (l < q.l) move(l++, -1);
        while (l > q.l) move(--l, 1);
        while (r < q.r) move(r++, 1);
        while (r > q.r) move(--r, -1);
        ans[q.id] = nowAns;
    }
}

BZOJ 2120

树上莫队

对于树上的路径询问问题,如果能够在 O(1)O(1) 的时间内加入、删除一个点的贡献,那么就可在 O(nn)O(n\sqrt n) 的复杂度内求出所有询问的答案。

实现:离线后排序,顺序遍历询问,暴力转移路径。

如何转移路径?设 TuT_uuu 到根的路径上边的集合,那么 uuvv 的路径上边的集合就是 TuTvT_u \bigtriangleup T_v\bigtriangleup 是对称差)。我们要从 uvu\rightarrow v 转移到 uvu'\rightarrow v',等价于这样的转移:

TuTvTuTv T_u \bigtriangleup T_v \rightarrow T_{u'} \bigtriangleup T_{v'}

根据对称差的性质,有 TuTuTu=TuT_u \bigtriangleup T_u \bigtriangleup T_{u'} = T_{u'},所以只需要如下变换即可:

TuTv(TuTu)(TvTv)=TuTv T_u \bigtriangleup T_v \bigtriangleup (T_u \bigtriangleup T_{u'}) \bigtriangleup (T_v \bigtriangleup T_{v'}) = T_{u'}\bigtriangleup T_{v'}

落实到程序上面,用 in[u]\mathrm{in}[u] 记录点 uu 到父亲的边有没有被算进集合,从 uvu\rightarrow v 转移到 uvu'\rightarrow v' 的时候,暴力遍历路径 uuu \rightarrow u' 和路径 vvv \rightarrow v' 上的边,如果一条边已经加入,那么删掉它,如果没有加入,就加入它。这样就实现了对称差运算。

排序方法:按照 BZOJ 1086 的方法将树分块,设定块的大小为 SS。按照 (blockID(u),dfn(v))(\mathrm{blockID}(u), \mathrm{dfn}(v)) 的二元组从小到大排序。
复杂度分析:有两种块,一个是树上的块,一个是询问序列中的块(第一关键字相同)。我们单独考虑询问序列中的每个块。每个询问中的 uu 属于同一个树上的块。先考虑对于 uu 的移动,由于树上的块内任意两个点之间的路径长度是 O(S)O(S) 的,所以每个询问,uu 点移动的路径长度为 O(S)O(S)。对于 vv 的移动,块内每个询问的 dfn(v)\mathrm{dfn}(v) 是递增的,我们知道,顺序走一边 DFS 序上的每个点,相当于每条边都被走了 2 次,所以每个块中 vv 移动的路径长度是 O(n)O(n) 的。一共有 O(nS)O(\frac n S) 个块,相邻块之间转移的复杂度为 O(n)O(n),总复杂度:O(mS+n2S+n2S)O(mS + \frac {n^2} S + \frac {n^2} S),不妨设 n,mn, m 同阶,取 S=nS = \sqrt n 可达到最优复杂度 O(nn)O(n\sqrt n)

代码

int u = 0, v = 0, nowAns = 0;
bool in[MAX_N];

inline void flip(int u) {
    // if u in S: remove u
    // else insert u
    // update nowAns
}

inline int move(int u, int v) {
    int lca = LCA(u, v);
    for (int cur = u; cur != lca; cur = anc[0][cur])
        flip(cur);

    for (int cur = v; cur != lca; cur = anc[0][cur])
        flip(cur);
}

void solve() {
    BLOCK_SIZE = int(ceil(pow(n, 0.5)));
    sort(querys, querys + m);
    for (int i = 0; i < m; ++i) {
        const query &q = querys[i];
        int lca = LCA(q.u, q.v);
        move(u, q.u), move(v, q.v);
        ans[q.id] = nowAns;
        u = q.u, v = q.v;
    }
}

BZOJ 3757

树上带修改莫队

考虑树上莫队带修改,如果能 O(1)O(1) 的应用以及撤销修改,那么可以在 O(n53)O(n^{\frac 5 3}) 的复杂度内求出所有询问的答案。思路与普通带修改莫队是类似的。

实现:离线后排序,顺序遍历询问,先将时间转移到当前询问的时间,接着暴力转移路径。
排序方法:将树分块,设定块的大小为 SS。按照 (blockID(u),blockID(v),t)(\mathrm{blockID}(u), \mathrm{blockID}(v), t) 的三元组从小到大排序。
复杂度分析:我们考虑询问序列中的每个块(一二关键字相同),每个询问 uuvv 移动的距离都是 O(S)O(S) 的,整个块时间最多变化 mm。一共有 O(n2s2)O(\frac {n^2} {s^2}) 个块,相邻块之间转移的复杂度为 O(n)O(n),总复杂度:O(mS+mS+n2ms2+n2ms2)O(mS + mS + \frac {n^2m} {s^2} + \frac {n^2m} {s^2}),不妨设 n,mn, m 同阶,取 S=n23S = n ^ {\frac 2 3} 时可达到最优复杂度 O(n53)O(n^{\frac 5 3})

代码

int u = 0, v = 0, t = 0, nowAns = 0;
bool in[MAX_N];

inline void flip(int u) {
    // if u in S: remove u
    // else insert u
    // update nowAns
}

inline void moveTime(int t, int sign) {
    // apply or revoke modifications
    // update nowAns
}

inline void move(int u, int v) {
    int lca = ::lca(u, v);

    for (int cur = u; cur != lca; cur = anc[0][cur])
        flip(cur);

    for (int cur = v; cur != lca; cur = anc[0][cur])
        flip(cur);
}

void solve() {
    BLOCK_SIZE = int(ceil(pow(n, 2.0 / 3)));
    sort(querys, querys + m);
    for (int i = 0; i < q2; ++i) {
        const query q = querys[i];
        while (t < q.t) moveTime(t++, 1);
        while (t > q.t) moveTime(--t, -1);
        int lca = LCA(q.u, q.v);
        move(q.u, u), move(q.v, v);
        ans[q.id] = nowAns;
        u = q.u, v = q.v;
    }
}

BZOJ 3052