Sengxian's Blog

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

概述

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

形式

普通莫队

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

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

实现：离线后排序，顺序遍历询问，先将时间转移到当前询问的时间，然后再像普通莫队一样转移区间。
排序方法：设定块的长度为 $S_1$ 和 $S_2$，按照 $(\lfloor\frac l {S_1}\rfloor, \lfloor\frac r {S_2}\rfloor, t)$ 的三元组小到大排序，其中 $t$ 表示这个询问的时刻之前经历过了几次修改操作。
复杂度分析：考虑询问序列中的每个小块，小块内每个询问的一二关键字相同。在这个小块内，显然 $t$ 最多变化 $m$，对于每个询问，$l, r$ 最多变化 $S_1$ 和 $S_2$，一共有 $\frac {n^2} {S_1S_2}$ 个这样的块，相邻块之间转移的复杂度为 $O(n)$，总复杂度就是 $O(mS_1 + mS_2 + \frac {n^2m} {S_1S_2} + \frac {n^3} {S_1S_2})$，不妨设 $n, m$ 同阶，取 $S_1 = S_2 = n ^ {\frac 2 3}$ 时可达到最优复杂度 $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(n\sqrt n)$ 的复杂度内求出所有询问的答案。

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

如何转移路径？设 $T_u$ 为 $u$ 到根的路径上边的集合，那么 $u$ 到 $v$ 的路径上边的集合就是 $T_u \bigtriangleup T_v$（$\bigtriangleup$ 是对称差）。我们要从 $u\rightarrow v$ 转移到 $u'\rightarrow v'$，等价于这样的转移：

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

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

排序方法：按照 BZOJ 1086 的方法将树分块，设定块的大小为 $S$。按照 $(\mathrm{blockID}(u), \mathrm{dfn}(v))$ 的二元组从小到大排序。
复杂度分析：有两种块，一个是树上的块，一个是询问序列中的块（第一关键字相同）。我们单独考虑询问序列中的每个块。每个询问中的 $u$ 属于同一个树上的块。先考虑对于 $u$ 的移动，由于树上的块内任意两个点之间的路径长度是 $O(S)$ 的，所以每个询问，$u$ 点移动的路径长度为 $O(S)$。对于 $v$ 的移动，块内每个询问的 $\mathrm{dfn}(v)$ 是递增的，我们知道，顺序走一边 DFS 序上的每个点，相当于每条边都被走了 2 次，所以每个块中 $v$ 移动的路径长度是 $O(n)$ 的。一共有 $O(\frac n S)$ 个块，相邻块之间转移的复杂度为 $O(n)$，总复杂度：$O(mS + \frac {n^2} S + \frac {n^2} S)$，不妨设 $n, m$ 同阶，取 $S = \sqrt n$ 可达到最优复杂度 $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(n^{\frac 5 3})$ 的复杂度内求出所有询问的答案。思路与普通带修改莫队是类似的。

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