莫队 学习笔记

发表于 更新于 分类于 Waline：
摘要：莫队、带修莫队、回滚莫队…

莫队

莫队算法是由莫涛提出的数据结构。在莫涛提出莫队算法之前，莫队算法已经在 Codeforces 的高手圈里小范围流传，但是莫涛是第一个对莫队算法进行详细归纳总结的人。莫涛提出莫队算法时，只分析了普通莫队算法，但是经过 OIer 和 ACMer 的集体智慧改造，莫队有了多种扩展版本。

普通莫队

如果已知 [l,r][l,r] 的答案，能在很小的时间复杂度内得到 [l+1,r],[l−1,r],[l,r+1][l+1,r],[l-1,r],[l,r+1] 以及 [l,r−1][l,r-1] 的答案，便可以使用莫队。

莫队只能离线解决问题，所以不适用于强制在线的题目。

莫队的执行过程大致如下：

  1. 将所有询问按照一种神奇的顺序排序；
  2. 将当前区间设为 [1,1][1,1]；
  3. 不停移动左右端点，使得区间与第一个询问重合，记录此时的答案。
  4. 用相同的方法，继续移动左右端点，求出所有询问的答案。

而第 1 步中“神奇的顺序”指什么呢？

假设序列长度为 nn，询问次数为 mm，我们假设 n,mn,m 同阶。

将序列分块，分成 n\sqrt n 个块。将询问按照左端点所在块的编号为第一关键字，右端点位置为第二关键字排序。

关于块长的选取和时间复杂度证明

我们设块长为 ss，左端点在第 ii 个块中的询问数量为 qiq_i，块的数量是 ns\dfrac{n}{s}。

对于第 ii 个块来说，左端点在块内移动，最坏情况下每次都移动 ss 步。右端点是有序的，所以最坏情况下总共移动 nn 次，时间复杂度为 qi×s+nq_i\times s+n。

对于这 ns\dfrac{n}{s} 个块，总时间复杂度为 ∑i=1ns(qi×s+n)=(∑i=1nsqi)×s+(n×ns)=m×s+n2s\sum_{i=1}^{\frac{n}{s}} (q_i\times s+n)=(\sum_{i=1}^{\frac{n}{s}}q_i) \times s + (n\times \dfrac{n}{s})=m\times s + \dfrac{n^2}{s}。假设 n,mn,m 同阶，则时间复杂度表示为 n×s+n2sn\times s + \dfrac{n^2}{s}。

所以，当 n×s=n2sn\times s=\dfrac{n^2}{s} ，即 s=ns=\sqrt n 时，总时间复杂度最小。将 ss 带入原式，得到时间复杂度为 Θ(nn)\Theta(n\sqrt n)。

莫队具体如何实现，我将借助于一道题：Luogu P2709 来讲解。

首先，创建结构体来记录所有询问：

1
2
3
4
struct Q
{
    int l, r, id;//l:左端点  r:右端点  id:这个询问的编号
}q[50010];

然后，写两个函数：add(x) 和 del(x)，表示添加或删除数字 xx，函数里计算添加或删除 xx 后的答案。这样就可以顺利地移动区间。

1
2
3
4
5
6
7
8
9
10
11
int cnt[50010], res;//表示区间内每个数字出现的次数、当前的答案
void add(int x)
{
    res = res - cnt[x] * cnt[x] + (cnt[x] + 1) * (cnt[x] + 1);
    cnt[x]++;
}
void del(int x)
{
    res = res - cnt[x] * cnt[x] + (cnt[x] - 1) * (cnt[x] - 1);
    cnt[x]--;
}

然后，对于每一个询问，我们先移动区间，直到当前区间与询问重合，保存答案。循环中前四行的顺序很重要，一定要先执行 r++、l--，再执行 r--、l++，否则可能出现 l>rl>r 的情况。

1
2
3
4
5
6
7
8
9
10
int l = 1, r = 1;
add(a[1]);//一定记住写这一行，因为当前区间为[1,1],包括第一个数字
for(int i = 1; i <= m; i++)
{
    while(r < q[i].r) r++, add(a[r]);
    while(l > q[i].l) l--, add(a[l]);
    while(r > q[i].r) del(a[r]), r--;
    while(l < q[i].l) del(a[l]), l++;
    ans[q[i].id] = res;
}

然后，这道题就顺利的写完啦。

完整代码 
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
48
49
50
51
52
53
54
55
56
57
58
#include<bits/stdc++.h>
using namespace std;
struct Q
{
    int l, r, id;
}q[50010];
int cnt[50010], ans[50010], res;
int a[50010];
int S;
void add(int x)
{
    res = res - cnt[x] * cnt[x] + (cnt[x] + 1) * (cnt[x] + 1);
    cnt[x]++;
}
void del(int x)
{
    res = res - cnt[x] * cnt[x] + (cnt[x] - 1) * (cnt[x] - 1);
    cnt[x]--;
}

bool cmp(Q a, Q b)
{
    if(a.l / S != b.l / S)
        return a.l / S < b.l / S;
    else 
        return a.r < b.r;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    int n, m, k;
    cin >> n >> m >> k;
    for(int i = 1; i <= n; i++) cin >> a[i];
    
    for(int i = 1; i <= m; i++) cin >> q[i].l >> q[i].r, q[i].id = i;
    
    S = sqrt(n);
    
    sort(q + 1, q + 1 + m, cmp);
    
    int l = 1, r = 1;
    add(a[1]);
    for(int i = 1; i <= m; i++)
    {
        while(r < q[i].r) r++, add(a[r]);
        while(l > q[i].l) l--, add(a[l]);
        while(r > q[i].r) del(a[r]), r--;
        while(l < q[i].l) del(a[l]), l++;
        ans[q[i].id] = res;
    }
    for(int i = 1; i <= m; i++) 
        cout << ans[i] << endl;
    
    return 0; 
}

但是我们发现，当处理完左端点所在的块为 ii 的所有询问后，右端点可能会从最右面回到最左面，这样就很不好。

所以我们有一个优化方式：判断左端点所在的块的奇偶性。如果是奇数，则按右端点位置从小到大排序，否则按从大到小排序。

------待更新------