「算法笔记」莫队算法

发表于 | | 阅读次数:
字数统计: 1.3k 字
莫队算法，通过对询问离线、分块和排序，看似暴力却能巧妙优化复杂度。

概述

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

例题

我们以 「国家集训队 2009」小 Z 的袜子 为例。

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

数据范围：$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$ 以 $\Theta(\sqrt{n})$ 的大小进行分块，记第 $i$ 个询问左端点所在的块为 $b_i$，以 $b_i$ 为第一关键字，$r_i$ 为第二关键字进行排序。那么整体的 $b_i$ 是有序的，同一个块中的 $r_i$ 是有序的。

询问

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

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

证明

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

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

左端点

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

右端点

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

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

代码

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

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
 
#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 ques {
    int l,r,id;
    bool operator < (const ques &rhs) const {
        return b[l]==b[rhs.l]?r<rhs.r:l<rhs.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];}
long long gcd(long long x,long long y) {return y?gcd(y,x%y):x;}

int main() {
    scanf("%d%d",&n,&m);
    int len=sqrt(n);
    for(int i=1;i<=n;++i) b[i]=(i-1)/len+1;
    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;
    std::sort(q+1,q+m+1);
    int l=1,r=0;
    for(int i=1;i<=m;++i) {
        int x=q[i].l,y=q[i].r;
        if(x==y) {
            ansx[q[i].id]=0;
            ansy[q[i].id]=1;
            continue;
        }
        while(x<l) add(a[--l]);
        while(x>l) del(a[l++]);
        while(y<r) del(a[r--]);
        while(y>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=gcd(ansx[i],ansy[i]);
        printf("%lld/%lld\n",ansx[i]/d,ansy[i]/d);
    }
    return 0;
}

习题

扩展

如果我们把块的大小设为 $\Theta\left(\dfrac{n}{\sqrt{m}}\right)$，那么莫队算法的复杂度为 $O(n\sqrt m)$（复杂度分析同上）。

0%