莫队学习笔记_莫队的复杂度

前言：莫队也不难

这里只讲基础莫队，待修的就鸽了

马蜂比较奇怪，轻喷。

文章同步于Luogu博客。

码字不易，点个赞吧。

Part 1 基础思想

莫队，俗称“优雅的暴力”，它其实就只是在暴力算法的基础上做了一点小小的优化。平均复杂度为：$\Theta (n^{\frac{1}{2}}\ast q)$ ，也就是 $\Theta (q\sqrt{n})$ 。

所以说有时候出题人是可以卡掉莫队的。

---

1.1 “暴力”思想

题目：假如我现在有一个数列 $a$ 长度为 $n$ ，有 $q$ 次询问 然后每次给定一个区间 $[x,y]$ ，求这个区间里有多少个不同的数。

本题当然可以用线段树做，但是莫队的功能会比线段树更强大，虽然说莫队的复杂度会比线段树高 。

那么这道题的最朴素的暴力算法就是它给几个区间就算几个，复杂度为 $\Theta (nq)$，但是我们有没有想过一个问题：我们前面求的答案对后面的答案是否有帮助呢？

答案是有的

那么有什么关系呢？

举个例子，数列为 1 3 2 2 3 4 2 1，要查询 $3$ 个区间，分别是 $[1,4][2,6][3,4]$

假设我们现在有两个指针： $l$ 和 $r$ 。（数组从 $1$ 开始）

$r$ 指向 $0$ ， $l$ 指向 $1$ 。

由于第一个要查 $[1,3]$ ，那么我们就得把 $l$ 移动到 $1$ 上， $r$ 移动到 $3$ 上，但是我们怎么移呢？

我们再开一个数组 $cnt$ ， $cn{t}_i$ 表示数字 $i$ 再 $[l,r]$ 区间内出现了几次。我们每将 $r$ 向右移完一格后，我们就 cnt[a[r]]++， 这时候如果 cnt[a[r]] == 1，那么就说明 a[r]以前没有在 $[l,r]$ 这个区间内出现过，那么我们的 $ans$ 就 $+1$。

同时， $l$ 向右移的时候也是这样的，如果右移完后 cnt[a[l - 1]] == 0，那就说明 a[l - 1]在区间 $[l,r]$ 里已经没有了，那么就 $ans-1$。

$l$ 左移， $r$ 右移也是一样的。

现在来模拟一遍：
（我们一般先移 $r$ ，再移 $l$）

初始状态：

这个时候 $[l,r]$ 区间内没有数，所以$ans=0$

cnt = [0, 0, 0, 0]

（这里所有显示的 $cnt$ 下标都是从 $1$ 开始）

第一步： $r$ 右移一位

（这里 $l$ 和 $r$ 在同一个位置上）

这个时候就得 cnt[r]++了，且由于 cnt[r] == 1，所以 ans++，故 $ans=1$ 。

cnt = [1, 0, 0, 0]

第二步： $r$ 再右移一位

同样，cnt[r]++。因为 cnt[r] == 1，所以 ans++， ans = 2。

cnt = [1, 0, 1, 0]

第三步： $r$ 继续右移

cnt = [1, 1, 1, 0]

ans = 3

第四步：$r$ 右移

注意，这里由于 cnt[r]++后 cnt[r] == 2，所以 $ans$ 不应该 $+1$ 。

cnt = [1, 2, 1, 0]

这时候，ans = 3，这就是答案。

注意！！！：每次跑完一个数据时不要将 $l$ 和 $r$ 重置，要继续移动 $l$ 和 $r$ 到下一个询问的指定位置。显然，这样的时间复杂度更优。

---

1.2 “暴力”的复杂度分析以及莫队算法

1.2.1 “暴力”的复杂度

我们现在把所有询问的的左右端点用一个平面直角坐标系表示出来：

还是用原来的样例：

那么我们可以算算，它的运算次数就是从 $(0,0)$ 到 $(1,4)$ 到 $(2,6)$ 到 $(3,4)$ 的曼哈顿距离之和。

也就是红线的距离之和，为 $11$ 。

但是我们有没有一种复杂度更低的算法呢？

答案是有的：

如果我们从 $(0,0)$ 到 $(1,4)$ 到 $(3,4)$ 到 $(2,6)$ ， 再算算它的的曼哈顿距离之和。

那么我们的距离就只有 $10$ 了。

所以说决定我们复杂度的，是我们的点的遍历顺序！

---

1.2.2 莫队算法

莫队算法就是改变每个点的遍历顺序来优化时间复杂度。

那么怎么优化呢？

这里需要用一下我们之前讲的分块。

我们依然把所有区间按左端点分为 $\sqrt{n}$ 块，我们在每个块内按每个区间的左端点从小到大排序即可。

普通莫队时间复杂度分析：

$l$ 跨块转移的次数 $O(\sqrt{n})$ ，跨块转移的总距离为 $O(n)$ ，即不跨块转移的次数为 $O(n-\sqrt{n})$ ，每次的查询的复杂度是 $O(\sqrt{n})$ 。

所以 $l$ 的时间复杂度为 $O(n)+O(n-\sqrt{n})\ast O(\sqrt{n})=\Theta (n\sqrt{n})$ 。

同理， $r$ 的时间复杂度为 $\Theta (n\ast \sqrt{n})$ 。

所以总的时间复杂度为 $\Theta (n\ast \sqrt{n})$ 。

（注：一般题目的 $n$ 和 $q$ 的范围是一样的，所以这里把 $q$ 也写成了 $n$ 。）

这里还有一个优化：奇偶优化

就是每次跨块的时候都有 $\Theta (n)$ 的复杂度，那么我们就可以让第奇数块从小到大排序，第偶数块从大到小排序，这样就可以在一定程度上避免跨块时的复杂度。

所以说莫队还有一个好处就是即使你排序写挂了你最多复杂度跟不上而不至于全WA

Part 2 代码实现

注释全在代码里了qwq。

同时，这也是SP3267的代码。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstdlib>
#include<cmath>
#include<iomanip>
#include<cstring>
#include<unordered_map>
#include<map>
#define sort stable_sort
#define ll long long
using namespace std;

struct poi // 记录每次询问
{
    int x; // 每次询问的左端点
    int y; // 每次询问的右端点
    int now; // 记录这是第几次询问
};

int n;
int a[30010]; // 原数组
int q;
int cnt[1000010];
int aans[200010]; // 最后的答案
poi que[200010]; // 询问
int ans;
int l = 1;
int r = 0;
int lll[200010]; // 分块中每块的l
int rrr[200010]; // 分块中每块的r
int pos[200010];
int num;
int kcnt; // 分块中块的个数

void init() // 分块的预处理，详见分块的blog
{
    num = sqrt(n);
    kcnt = n / num;
    if(n % num != 0)
    {
        kcnt++;
    }
    for(int i = 1; i <= kcnt; i++)
    {
        lll[i] = (i - 1) * num + 1;
        rrr[i] = lll[i] + num - 1;
    }
    rrr[kcnt] = n;
    for(int i = 1; i <= kcnt; i++)
    {
        for(int j = lll[i]; j <= rrr[i]; j++)
        {
            pos[j] = i;
        }
    }
}

bool cmp(poi x, poi y) // 排序
{
    if(pos[x.x] != pos[y.x]) // 如果x和y不在同一块内
    {
        return pos[x.x] < pos[y.x]; // 按x坐标排序
    }
    if(pos[x.x] & 1) // 奇偶优化
    {
        return x.y < y.y;
    }
    return x.y < y.y;
}

void add(int id) // 在[l,r]区间内加上下标为id一个数
{
    if(cnt[a[id]] == 0) // 如果加上这个数之前这个数没有出现过
    {
        ans++; // 加上这个数后不同的数的个数就要+1了
    }
    cnt[a[id]]++; // 加上后这个数要+1
}

void del(int id) // 在[l,r]区间内去掉一个下标为id的数
{
    if(cnt[a[id]] == 1) // 如果去掉前这个数只有一个
    {
        ans--; // 去掉后这个数就没有了，所以ans--
    }
    cnt[a[id]]--; // 去掉后这个数的个数要-1
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    cin >> q;
    for(int i = 1; i <= q; i++)
    {
        cin >> que[i].x >> que[i].y;
        que[i].now = i; // 记录每个块是第几个输入的，输出的时候要用
    }
    init(); // 分块
    sort(que + 1, que + q + 1, cmp); // 将区间排序
    for(int i = 1; i <= q; i++)
    {
        int x = que[i].x;
        int y = que[i].y;
        /*
        注意每次 l和r左移右移 和 加上l和r的所在数 的先后顺序！
        如果是add那么是先移再加
        若果是del那么是先减再移
        原因可以自己想想
        */
        while(l < x) // 如果l在区间的左端点的左边
        {
            del(l); // 减去l所在的这个数，因为l右移完后原来的l所在的数就不会再在[l,r]这个区间里面了
            l++; // 将l右移
        }
        while(l > x) // 如果l在区间的左端点的右边
        {
            l--; // 将l左移
            add(l); // 加上l左移完后加上l所在的数
        }
        while(r < y) // 如果r在区间的右端点的左边
        {
            r++; // 将r右移
            add(r); // 加上r移完后r所在的数
        }
        while(r > y) // 如果r在区间的右端点的右边
        {
            del(r); // 减去r移之前的r的所在数
            r--; // 将r左移
        }
        aans[que[i].now] = ans; // 记录这个区间的答案，输出要用
    }
    for(int i = 1; i <= q; i++)
    {
        cout << aans[i] << endl; // 按输入的顺序输出
    }
    return 0;
}
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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146

Part 3 一些关于莫队的题目

1.P3901 数列找不同

板子题，只需要判断不同的数的数量是不是等于区间的长度。

代码

2.P2709 小B的询问

也是板子题，改的地方只有 add和 del。

我们可以推一个式子：

$$a^2-(a-1{)}^2=$$
$$a^2-(a^2-2a+1)=$$
$$a^2-a^2+2a+1$$
$$2a+1$$

所以每多一个数就只要 ans += cnt[a[id]] + cnt[a[id]] + 1，每少一个数只要 ans -= cnt[a[id]] + cnt[a[id]] - 1即可。

代码

3.P7764 [COCI2016-2017#5] Poklon

也是只要改 add和 del，如果加之前个数为 $1$ ，那么 $ans+1$ ，个数为 $2$ ， $ans-1$ ；减之前个数为 $2$ ， $ans-1$ ，个数为 $3$ ， $ans+1$ 。

代码

一样，luogu上也有标签为“莫队”的题目，可以自己去做做

完结撒花✿✿ヽ(°▽°)ノ✿