Siyuan

「算法笔记」莫队算法
「算法笔记」莫队算法
扫描右侧二维码阅读全文
18
2018/11

「算法笔记」莫队算法

莫队算法,通过对询问离线、分块和排序,看似暴力却能巧妙优化复杂度。


概述

莫队算法的用武之地是一类询问可以离线,且可以通过区间 $[l,r]$ 的答案在 $\mathcal O(1)$ 或 $\mathcal O(\log n)$ 得到区间 $[l\pm 1,r]$ 或 $[l,r\pm 1]$ 的答案的问题。它通过对询问离线、分块和排序,巧妙地将时间复杂度从 $\mathcal O(nm)$ 优化到 $\mathcal O((n+m)\sqrt n)$。


例题

我们以「BZOJ 2038」小 Z 的袜子 为例。

小 Z 有 $n$ 只袜子,每只袜子都有一个颜色 $c_i$。他有 $m$ 次询问,每次询问给出一个区间 $[l,r]$,求出在这个区间里随机抽 $2$ 只袜子,这 $2$ 只袜子有多大的概率颜色相同。

数据范围:$1 \le n, m \le 5 \times 10^4$。


算法分析

例题中区间的信息没有区间可加性,因此无法用数据结构进行维护,

首先我们分析一下是否可以使用莫队解决,对于区间 $[l,r]$,答案为 $\dfrac{\sum_{i=1}^n \binom{f(i)}{2}}{\binom{r-l+1}{2}}$(其中 $f(i)$ 表示当前区间内颜色 $i$ 出现的次数)。如果要求出区间 $[l+1,r]$ 的答案,只比原先少了一个 $c_l$,我们把分子分母分开考虑:

  • 分子:在颜色 $c_l$ 中选择的方案数变少,减少了 $f(c_l)-1$ 种方案数。
  • 分母:就是新的区间长度 $r-l$ 中选 $2$ 个数的方案数 $\binom{r-l}{2}$。

对于向其他几种新区间的转移过程也是可以的,读者可以自行尝试分析。接下来我们就来了解一下莫队算法的过程!

排序

把所有的询问离线,把询问左端点 $l_i​$ 以 $\sqrt{n}​$ 的大小进行分块,记第 $i​$ 个询问左端点所在的块为 $b_i​$,以 $b_i​$ 为第一关键字,$r_i​$ 为第二关键字进行排序。那么整体的 $b_i​$ 是有序的,同一个块中的 $r_i​$ 是有序的。

询问

其实这个转移并没有什么技巧,反而非常非常非常暴力

如果我们已经知道了 $[L,R]$ 的信息,现在需要计算 $[l,r]$ 的答案,那我们直接把 $L$ 暴力移动到 $l$,把 $R$ 暴力移动到 $r$ 即可。

证明

了解完莫队的暴力转移过程,我们就要优美地证明这个过程并不暴力!

离线询问的整个过程中,只有 $L$ 和 $R$ 在不断移动并且两者独立,所以我们分别考虑。

左端点

  1. 相同块:左端点每次最多移动 $\mathcal O(\sqrt n)$ 的距离,有 $\mathcal O(m)$ 个询问。那么同一个块中左端点的移动距离为 $\mathcal O(m\sqrt n)$。
  2. 跨越块:左端点每次最多移动 $\mathcal O(\sqrt n)$ 的距离,有 $\mathcal O(\sqrt n)$ 次跨越块。那么跨越块导致左端点的移动距离为 $\mathcal O(n)$。

右端点

  1. 相同块:右端点每次最多移动 $\mathcal O(n)$ 的距离,有 $\mathcal O(\sqrt n)$ 个块。那么同一个块中右端点移动距离为 $\mathcal O(n\sqrt n)$。
  2. 跨越块:右端点每次最多移动 $\mathcal O(n)$ 的距离,有 $\mathcal O(\sqrt n)$ 次跨越块。那么跨越块导致右端点移动距离为 $\mathcal O(n\sqrt n)$。

综上所述,莫队算法的复杂度为 $\mathcal O((n+m)\sqrt n)$。

代码

莫队的代码非常套路,这份代码就当做是一个模板吧!

#include <cstdio>
#include <cmath>
#include <algorithm>

const int N = 5e4 + 5;

int n, m, a[N], b[N], cnt[N];
long long res, ansx[N], ansy[N];

struct Data {
    int l, r, id;
    bool operator < (const Data &b) const {
        return b[l] == b[b.l] ? r < b.r : l < b.l;
    }
} q[N];

long long query(int x) {
    return 1LL * x * (x - 1) / 2;
}
void add(int x) {
    res += cnt[x]++;
}
void del(int x) {
    res -= --cnt[x];
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    for (int i = 1; i <= m; i++) {
        scanf("%d%d", &q[i].l, &q[i].r);
        q[i].id = i;
    }
    int len = sqrt(n);
    for (int i = 1; i <= n; i++) {
        b[i] = (i - 1) / len + 1;
    }
    std::sort(q + 1, q + m + 1);
    for (int L = 1, R = 0, i = 1; i <= m; i++) {
        int l = q[i].l, r = q[i].r;
        if (l == r) {
            ansx[q[i].id] = 0;
            ansy[q[i].id] = 1;
            continue;
        }
        while(L > l) add(a[--L]);
        while(L < l) del(a[L++]);
        while(R > r) del(a[R--]);
        while(R < r) add(a[++R]);
        ansx[q[i].id] = res;
        ansy[q[i].id] = query(y - x + 1);
    }
    for (int i = 1; i <= m; i++) {
        long long d = std::__gcd(ansx[i], ansy[i]);
        printf("%lld/%lld\n", ansx[i] / d, ansy[i] / d);
    }
    return 0;
}

扩展

如果我们把块的大小设为 $\frac{n}{\sqrt{m}}$,那么莫队算法的复杂度为 $\mathcal O(n\sqrt m)$(复杂度分析同上)。

其实莫队还是可以支持单点修改的,详见「算法笔记」带修改莫队算法


习题

发表评论