Dyd's Blog

He who has a strong enough why can bear almost any how.

莫队

Posted on Edited on In
Symbols count in article: 8.8k Reading time ≈ 8 mins.

然而还没写完（不想填了）

莫队其实是一种基于分块的暴力思想，是一种离线算法，下面用例题来讲

例题一

P1972
（本题正解不是莫队，但我们可以用莫队玄学艹掉得86分）
抽象出下面一个问题：

有一个长为 $n$ 的数列 $A$ 和 $m$ 个询问，每个询问格式为 $l,r$ ，表示查询区间 $[l,r]$ 中不同的数有多少个。

本题的暴力做法灰常简单——对于每一个询问，扫描一遍数列，用一个 $cnt$ 数组统计每个数出现的次数，再扫描一遍 $cnt$ ，统计有多少个非零。时间复杂度为 $O(m（n+S))$ （其中 $S$ 表示 $cnt$ 数组的长度，即数据范围）。

一个简单的优化可以把 $S$ 去掉：
在统计时 $a_i$ 出现，判定 $cnt[a_i]$ 若为0， $ans++,cnt[a_i]++$ ,否则只是 $cnt[a_i]++$ 。则时间复杂度优化为 $O(mn)$

可是时间复杂度还是太大了，为此，我们用一个类似双指针的优化。

优化一

思考下面一种情况，上一个询问我们已经求出 $[i,j]$ （这里 $i,j$ 是两个指针）中不同的数的个数，储存在 $ans$ 中，并且 $cnt$ 已经跟新好了，现在我们要求 $[l,r]$ 。
求法当然是移动指针，具体如下：

  1. 将 $j$ 一步步向后走直到 $j=r$ ，并将 $cnt[a_j]++$ ，如果 $a_j$ 是新出现的，则 $res++$ 。

  2. 将 $i$ 一步步向后走直到 $i=l$ ，并将 $cnt[a_j]–$ ，如果 $cnt[a_j]=0$ ，则 $res–$ 。

以上方法最坏情况下的时间复杂度仍为 $O(mn)$ ，可恶啊，我们优化了个寂寞！

莫队

像我一样的蒟蒻们可能到这里就放弃了，但某国国家队的某莫涛队员dalao们却开始思考起来：为啥这个优化优化了个寂寞会到最坏情况呢？当然是因为查询的问题不确定，本个查询和上个查询的区间可能完全没有交集，甚至相隔甚远，这使得指针移动耗费了大量时间。于是，dalao们提出了解决方法——
既然查询的顺序会影响时间复杂度，那么我们调整一下查询顺序不就好了！

优化二

优化一的时间复杂度在 $O(n^2)$ ，而用了dalao的思路后可以优化为 $O(n\sqrt{n})$ 。

先读入所有查询，将二元组 $(l_i,r_i)$ 以 $r_i$ （也可以 $l_i$ ）为关键字排序，完成后以 $r_i$ 有序来查询，这样指针 $j$ 的跳转次数不超过 $n$ 次（因为不会来回跳转）。但指针 $i$ 怎么办呢？dalao也给出方法——不会就分块呗。

我们在排序时加入第二个关键字——分块的编号。我们以 $l_i$ 所在块的编号为第一关键字， $r_i$ 为第二关键字来从小到大排序。

综上，我们将所有的查询操作分成长度为 $\sqrt{n}$ 的 $\sqrt{n}$ 块，每一块内的 $r_i$ 是单调递增的。则每一块内部 $j$ 的跳转次数不超过 $n$ 次，共 $\sqrt{n}$ 块；在块内时 $i$ 的移动次数不超过块的长度，即 $\sqrt{n}$ ，而在跨块时移动次数不超过两块的长度，即 $2\sqrt{n}$。那么时间总复杂度为 $O(n\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
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
#include <bits/stdc++.h>
using namespace std;
const int N = 1000000 + 5;
int n, m, len;
int w[N], ans[N];
struct Question
{
    int id, l, r;
#define id(i) q[i].id
#define l(i) q[i].l
#define r(i) q[i].r
} q[N];
int cnt[N];
int read()
{
    char ch = getchar();
    int x = 0, f = 1;
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}
int get(int x)
{
    return x / len;
}
bool cmp(const Question &a, const Question &b)
{
    int i = get(a.l), j = get(b.l);
    if (i != j)
        return i < j;
    return a.r < b.r;
}
void add(int x, int &res)
{
    if (!cnt[x])
        res++;
    cnt[x]++;
}
void del(int x, int &res)
{
    cnt[x]--;
    if (!cnt[x])
        res--;
}
int main()
{
    n = read();
    for (int i = 1; i <= n; ++i)
        w[i] = read();
    m = read();
    len = sqrt((double)n * n / m); //len的长度很玄学,会直接影响时间复杂度
    for (int i = 0; i < m; ++i)
    {
        q[i].id = i;
        q[i].l = read();
        q[i].r = read();
    }
    sort(q, q + m, cmp);
    for (int k = 0, j = 0, i = 1, res = 0; k < m; ++k)
    {
        while (j < r(k))
            add(w[++j], res);
        while (j > r(k))
            del(w[j--], res);
        while (i < l(k))
            del(w[i++], res);
        while (i > l(k))
            add(w[--i], res);
        ans[id(k)] = res;
    }
    for (int i = 0; i < m; ++i)
        printf("%d\n", ans[i]);
    return 0;
}

例题二（带修改的莫队）

P1903

新指针

本题多了一种操作，即可以修改数列 $A$ 的元素。
为了解决该问题，我们给询问加一维 $k$ ，即询问 $l\ r\ k$ 表示“在第 $k$ 次修改后 $[l,r]$ 中不同的数的个数”，那么我们用三个指针（ $i,j,k$ ）来跳转。

指针 $i,j$ 都很好跳转，但 $k$ 的跳转我们必须认真分析一下了：
当 $k$ 从 $t-1$ 跳转到 $t$ 时，由于每次操作只会修改一个数的值（设为 $a_x$ ），那么如果 $x\in[l,r]$ 那么我们就必须更新 $cnt$ 和 $res$ 否则我们就不管它。跳转一次的时间复杂度为 $O(1)$ 。

但是，问题又双叒叕来了——重 $t$ 跳转会 $t-1$ 咋办？询问里面可没存原数列啊！不过，dalao有dalao的解决办法：设操作 $t$ 的修改是“把 $a_x$ 重 $y$ 修改为 $z$ ”，我们在修改完后交换 $y,z$ ，即让操作 $t$ 的修改变为“把 $a_x$ 重 $z$ 修改为 $y$ ”，这样，不管是加还是减，只要经过操作 $t$ 就执行即可。

排序

解决完新指针 $k$ 的问题后，聪明的dalao又开始思考新的问题了——该如何排序呢？

我们发现，只要以某一个指针为关键字，即让该指针单调，那么该扫描该指针的时间复杂度就会从 $O(n^2)$ 变成 $O(n)$ 。so，our思路还是让一个指针单调，其他指针分块。

所以排序变成一个三关键字排序：

  1. $l$ 所在块的编号

  2. $r$ 所在块的编号

  3. $t$

块的大小

然后，我们就来到了莫队里最玄学的地方——每一块该有多大呢？
像我一样的蒟蒻随便取个 $\sqrt{n}$ 或某个常数就可以了。
但总有像 xyc 一样的dalao喜欢秀智商严谨计算：

设每一块的大小为 $b$ ，则块的数量为 $\frac{n}{b}$ 。
那么，指针 $i$ （对应 $l$ ） 在块内移动的次数最大为 $b$ 有 $m$ 个问题，跨块的话每次最多移动 $2b$ （两个块的长度），有 $\frac{n}{b}$ 块，所以总的时间复杂度为 $O(b\times m+2b\times \frac{n}{b})=O(bm+n)$ 。

指针 $j$ 的情况有点复杂。 $j$ 在块内和 $i$ 一样，最多为 $am$ 。但块间移动时，对于 $i$ 的每一个块， $j$ 最坏都会从第1块移动到第 $\frac{n}{b}$ 块，每次块间移动为 $O(2b \times \frac{n}{b})=O(n)$ ， $i$ 共有 $\frac{n}{b}$ 块，所以共为 $\frac{n^2}{b}$ ，总的时间复杂度为 $O(bm+\frac{n^2}{b})$

指针 $k$ 的在 $l,r$ 确定的情况下是单调的，最多移动 $t$ 次。而 $l,r$ 各有 $\frac{n}{b}$ 种情况，故总时间复杂度为 $O(\frac{n^2}{b^2}t)$

那么，如何取 $b$ 使 $max(O(bm+n),O(bm+\frac{n^2}{b}),O(\frac{n^2}{b^2}t))$ 最小呢？
由于 $m=n,bm>n$ ，不妨化简为 $O(bn),O(bn+\frac{n^2}{b}),O(\frac{n^2}{b^2}t)$ 。
如果 $b\le \sqrt{n}$ ，则 $\frac{n^2}{b^2}t \ge nt$ 时间复杂度为 $O(n^2)$ 级别，过大，故必须保证 $b \ge \sqrt{n}$ 。
那么就有 $\frac{n^2}{b} \le bn$ ，故 $O(bn+\frac{n^2}{b})$ 可化为 $O(bn)$ 。
现在只需要比较 $bn$ 和 $\frac{n^2}{b^2}t$ ，使二者的最大值最小，只需解一个方程 $bn=\frac{n^2}{b^2}t$ ，解得 $b=\sqrt[3]{nt}$ 。

综上，当 $b=\sqrt[3]{nt}$ 时，时间复杂度最优为 $O(\sqrt[3]{n^4t})\approx 10^6\sim10^7$ 。

代码

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
#include <bits/stdc++.h>
using namespace std;
const int N = 133333 + 5, S = 1000000 + 5;
int n, m, mq, mc, len;
int w[N], cnt[S], ans[N];
struct Question
{
    int id, l, r, t;
} q[N];
struct Modify
{
    int p, c;
} c[N];
int get(int x)
{
    return x / len;
}
bool cmp(const Question &a, const Question &b)
{
    int al = get(a.l), ar = get(a.r);
    int bl = get(b.l), br = get(b.r);
    if (al != bl)
        return al < bl;
    if (ar != br)
        return ar < br;
    return a.t < b.t;
}
void add(int x, int &res)
{
    if (!cnt[x])
        res++;
    cnt[x]++;
}
void del(int x, int &res)
{
    cnt[x]--;
    if (!cnt[x])
        res--;
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", &w[i]);
    for (int i = 0; i < m; i++)
    {
        char op[2];
        int a, b;
        scanf("%s%d%d", op, &a, &b);
        if (*op == 'Q')
            mq++, q[mq] = {mq, a, b, mc};
        else
            c[++mc] = {a, b};
    }
    len = cbrt((double)n * max(mc, n));
    sort(q + 1, q + mq + 1, cmp);
    for (int i = 0, j = 1, t = 0, k = 1, res = 0; k <= mq; k++)
    {
        int id = q[k].id, l = q[k].l, r = q[k].r, tm = q[k].t;
        while (i < r)
            add(w[++i], res);
        while (i > r)
            del(w[i--], res);
        while (j < l)
            del(w[j++], res);
        while (j > l)
            add(w[--j], res);
        while (t < tm)
        {
            t++;
            if (c[t].p >= j && c[t].p <= i)
            {
                del(w[c[t].p], res);
                add(c[t].c, res);
            }
            swap(w[c[t].p], c[t].c);
        }
        while (t > tm)
        {
            if (c[t].p >= j && c[t].p <= i)
            {
                del(w[c[t].p], res);
                add(c[t].c, res);
            }
            swap(w[c[t].p], c[t].c);
            t--;
        }
        ans[id] = res;
    }
    for (int i = 1; i <= mq; i++)
        printf("%d\n", ans[i]);
    return 0;
}

例题三（回滚莫队）

看看下题
AT1219
本题中区间伸长的时候很好维护信息但区间缩短的时候不太好维护信息
于是我们遇到莫队的一个常见问题：当询问的不再是简单的计数，而是最值或其他带有比较性质的信息时，如何在指针移动时用可接受的时间实现答案的跟新（即“当前区间”的插入和删除时如何快速跟新答案）？
就本题而言，我们发现插入一个新数的跟新非常简单：

1
2
cnt[i]++;
if(cnt[i]*i>res) res=cnt[i]*i;

但是，删除操作会变得十分麻烦：原来 $res=cnt[i]$ ，但当 $cnt[i]-=i$ 后， $res$ 就必须要把整个 $cnt$ 数组扫描一遍才能确定。
当然，dalao可以用二叉堆来解决这个问题，但其实莫队有一种 虽然时间慢些 更好写的办法。

处理

首先分块，把询问区间先按左端点（ $l$ ）的块排序，相同按右端点（ $r$ ）从小到大排序

若询问的左右端点在同一个块内，暴力解决， $O(\sqrt{n})$
同块暴力

剩下的询问必然是跨块的，如图：跨块暴力
由于排序，对于 $l$ 同块的询问 $r$ 一定是递增的，其指针在转移时不必考虑删除操作（如图中 $r_{i+1}$ 一定在 $r_i$ 右方），只需单独定一个 $cnt2$ 来记录即可；而 $l_{i+1}$ 有可能在 $l_i$ 左侧，但它们一定在同一块，即使涉及删除也不会多次使用。但，到底还是要删除，咋办？

想想你在玩 $galgame$ 玩出最坏的 $BE$的时候，你是不是会选择回档？想想为毛这东西要叫回滚莫队？想想到底是 $cnt$ 难删除还是 $res$ 那维护？于是，我们 在dalao的提示下 发现，我们也可以让莫队“回档”。
综上，操作如下：

  1. 先将指针移动到 $l$ 所在块的末尾（具体来讲，设块尾为 $q$ 则 $i=q+1,j=q$ ，保证初始为空）

  2. 将 $res$ 备份存档

  3. 每遇到一个询问，我们先移动 $j$ （对应 $r$ ），这里只会涉及添加操作,移动时跟新 $cnt$ 和 $res$

  4. 移动 $i$ ，由于 $i$ 最初一定在 $l$ 右边，故只有添加操作，移动完毕后跟新询问的答案

  5. 将 $res$ 回复，将 $i$ 归位到 $i=q+1$ ，过程中回复 $cnt$

最后，如果我们当前这个询问的块是上一个询问的下一个块，即我们跨过了一个块，就直接清空 $cnt$ ，重新再来，重复上面的操作，只是块变成了下一个而已（有dalao说：“就相当于我们对于每一个块做一次莫队”）

代码

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
#include <bits/stdc++.h>
using namespace std;
const int N = 100000 + 5;
typedef long long LL;
int n, m, len;
int w[N], cnt[N];
LL ans[N];
struct Question
{
    int id, l, r;
#define id(k) q[k].id
#define l(k) q[k].l
#define r(k) q[k].r
} q[N];
vector<int> nums; //离散化用
inline int read()
{
    char ch = getchar();
    int x = 0;
    while (ch < '0' || ch > '9')
        ch = getchar();
    while (ch >= '0' && ch <= '9')
        x = x * 10 + ch - '0', ch = getchar();
    return x;
}
inline int get(int x)
{
    return x / len;
}
bool cmp(Question x, Question y)
{
    int i = get(x.l), j = get(y.l);
    if (i != j)
        return i < j;
    return x.r < y.r;
}
inline void add(int x, LL &res)
{
    cnt[x]++;
    res = max(res, (LL)cnt[x] * nums[x]);
}
int main()
{
    n = read(), m = read();
    len = sqrt(n);

    //离散化
    for (int i = 1; i <= n; ++i)
        w[i] = read(), nums.push_back(w[i]);
    sort(nums.begin(), nums.end());
    nums.erase(unique(nums.begin(), nums.end()), nums.end());
    for (int i = 1; i <= n; ++i)
        w[i] = lower_bound(nums.begin(), nums.end(), w[i]) - nums.begin();

    for (int i = 0; i < m; ++i)
    {
        int a = read(), b = read();
        id(i) = i, l(i) = a, r(i) = b;
    }
    sort(q, q + m, cmp);

    for (int x = 0; x < m;)
    {
        int y = x;
        while (y < m && get(l(y)) == get(l(x))) //完成后x~y就是同块的
            ++y;
        int right = get(l(x)) * len + len - 1; //本块右端点

        //暴力求块内
        while (x < y && r(x) < right)
        {
            LL res = 0;
            for (int k = l(x); k <= r(x); ++k)
                add(w[k], res);
            ans[id(x)] = res;
            for (int k = l(x); k <= r(x); ++k) //回复
                cnt[w[k]]--;

            x++;
        }

        //求跨块
        LL res = 0;
        int j = right, i = right + 1;
        while (x < y)
        {
            while (j < r(x)) //右指针只增不删
                add(w[++j], res);

            LL b_res = res; //存档
            while (i > l(x))
                add(w[--i], res);

            ans[id(x)] = res;

            //回复
            while (i < right + 1)
                cnt[w[i++]]--;
            res = b_res;

            x++;
        }

        memset(cnt, 0, sizeof cnt); //换块,清空
    }

    for (int i = 0; i < m; ++i)
        printf("%lld\n", ans[i]);

    return 0;
}

例四（树上莫队）有完没完

AcWing2536
与例一类似，只是区间变成了树上的一个路径。
那要是可以把树变成一个序列，并且路径就对应一个区间，那该有多好啊！（好假，一看就是dalao告诉的）

于是 dalao告诉 我们想到，可以用欧拉序列！（那系个啥？）

欧拉序列

名字挺高级的，其实就是一个DFS遍历，遍历时经过的节点顺序就是欧拉序列。
for example：
欧拉路径