分块与莫队学习笔记

发表于 更新于 分类于 阅读次数： 本文字数： 9.3k
分块是一种暴力的根号数据结构，而莫队就是基于分块的一种优雅的离线暴力算法。

分块算法

分块是一种暴力的优化算法，例如在区间修改和区间求和过程中，我们将数组分为 \(s\) 块，那么对于修改操作，我们将其分为三部分：最前面没有覆盖一整块的部分，中间的完整块，以及最后的没有覆盖一整块的部分。对于完整块，我们可以通过直接打上标记的形式代表对整个区间进行修改，而对于前后两部分，我们采取暴力的对数组进行修改的方式，这样区间修改的复杂度是 \(O(s + \frac{n}{s})\)。而对于查询操作，同样的道理，分为前后不完整块和中间的完整块，完整块使用区间和加上标记乘长度，而不完整的部分可以直接暴力查询，时间复杂度仍然为 \(O(s+\frac{n}{s})\)。可见，复杂度跟我们分块的数量有关，有均值不等式可得，\(s+\frac{n}{s}\ge 2\sqrt{n}\)，因此只要我们分为 \(\sqrt{n}\) 块，就可以达到 \(O(q\sqrt{n})\) 的总复杂度。

例题

#6280. 数列分块入门 4

给出一个长度为 \(n\) 的序列，进行 \(n\) 次操作，每次可以对一个区间的数加上 \(c\) ，或查询一个区间的数的和，模 \(c+1\)。

题解

模版题，接下来详细介绍一下分块的实现以及一些细节。

首先，我们分成 \(\sqrt{n}\) 块，每块大小为 \(\sqrt{n}\)，但是很多时候不能刚好分完，所以选择让最后一块的数量占满剩下的所有格子。我们维护一个 st[i] 和 ed[i] 表示每块的开头位置和结尾位置，同时给每一个位置打上标记 bel[i] ，代表它是第几块的。还需要设置一个总和数组 sum[i]，在初始赋值和不完整块更新时维护，以及一个标记数组 mark[i]，在更新完整块时使用。

分块时，由于每块长度为 \(\sqrt{n}\)，因此第 \(i\) 块的开头为 st[i] = n / sqn * (i - 1) + 1，结尾为 ed[i] = n / sqn * i，同时最后一个块的结尾为 \(n\)。

1
2
3
4
5
for (int i = 1; i <= sqn; i++) {
    st[i] = n / sqn * (i - 1) + 1;
    ed[i] = n / sqn * i;
}
ed[sqn] = n;

划分出起点和终点后，我们遍历每一块，标记每个位置属于哪一块，并且维护初始的 sum[i] 以及每块的大小 sz[i]。

1
2
3
4
5
6
7
for (int i = 1; i <= sqn; i++) {
    sz[i] = ed[i] - st[i] + 1;
    for (int j = st[i]; j <= ed[i]; j++) {
        bel[j] = i;
        sum[bel[j]] += a[j];
    }
}

然后就是区间修改和查询了，修改时一定不要忘记不完整块暴力更新整块的 sum[i]，完整块更新 mark[i]。首先判断是不是在同块内，这种情况下暴力更新，否则选择三段式更新。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
if (bel[l] == bel[r]) {
    for (int i = l; i <= r; i++) {
        a[i] += c;
        sum[bel[i]] += c;
    }
} else {
    for (int i = l; i <= ed[bel[l]]; i++) {
        a[i] += c;
        sum[bel[i]] += c;
    }
    for (int i = st[bel[r]]; i <= r; i++) {
        a[i] += c;
        sum[bel[i]] += c;
    }
    for (int i = bel[l] + 1; i < bel[r]; i++) {
        mark[i] += c;
    }
}

查询时也要注意，不完整块的查询需要加上 mark[i]，因为整个区间被修改过了，对于完整块就是加上 mark[i] * sz[i]，以及数组本身的 sum[i] 也不能忘。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
i64 ans = 0;
if (bel[l] == bel[r]) {
    for (int i = l; i <= r; i++) {
        ans += a[i] + mark[bel[i]];
    }
} else {
    for (int i = l; i <= ed[bel[l]]; i++) {
        ans += a[i] + mark[bel[i]];
    }
    for (int i = st[bel[r]]; i <= r; i++) {
        ans += a[i] + mark[bel[i]];
    }
    for (int i = bel[l] + 1; i < bel[r]; i++) {
        ans += mark[i] * sz[i] + sum[i];
    }
}
cout << ans % (c + 1) << "\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;

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

void solve() {
    int n;
    cin >> n;
    int sqn = sqrt(n);
    vector<i64> a(n + 1), sum(sqn + 1), mark(sqn + 1);
    vector<int> st(sqn + 1), ed(sqn + 1), bel(n + 1), sz(sqn + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= sqn; i++) {
        st[i] = n / sqn * (i - 1) + 1;
        ed[i] = n / sqn * i;
    }
    ed[sqn] = n;
    for (int i = 1; i <= sqn; i++) {
        sz[i] = ed[i] - st[i] + 1;
        for (int j = st[i]; j <= ed[i]; j++) {
            bel[j] = i;
            sum[bel[j]] += a[j];
        }
    }
    int m = n;
    while (m--) {
        int op, l, r, c;
        cin >> op >> l >> r >> c;
        if (op == 0) {
            if (bel[l] == bel[r]) {
                for (int i = l; i <= r; i++) {
                    a[i] += c;
                    sum[bel[i]] += c;
                }
            } else {
                for (int i = l; i <= ed[bel[l]]; i++) {
                    a[i] += c;
                    sum[bel[i]] += c;
                }
                for (int i = st[bel[r]]; i <= r; i++) {
                    a[i] += c;
                    sum[bel[i]] += c;
                }
                for (int i = bel[l] + 1; i < bel[r]; i++) {
                    mark[i] += c;
                }
            }
        } else {
            i64 ans = 0;
            if (bel[l] == bel[r]) {
                for (int i = l; i <= r; i++) {
                    ans += a[i] + mark[bel[i]];
                }
            } else {
                for (int i = l; i <= ed[bel[l]]; i++) {
                    ans += a[i] + mark[bel[i]];
                }
                for (int i = st[bel[r]]; i <= r; i++) {
                    ans += a[i] + mark[bel[i]];
                }
                for (int i = bel[l] + 1; i < bel[r]; i++) {
                    ans += mark[i] * sz[i] + sum[i];
                }
            }
            cout << ans % (c + 1) << "\n";
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

P2801 教主的魔法

题目可以进行区间修改或区间查询操作，区间查询查询给定区间内大于等于 \(c\) 的值的数量。

题解

区间修改基本类似，对于查询，不完整块的暴力显然是成立的，而完整块可以通过排序后二分，就可以找到所有大于等于 \(c\) 的值的数量。然而，每次查询都进行排序显然会 TLE，实际上，初始对于每一块排序后，接下来的操作中我们只需要在不完整块的修改后进行排序即可，对于完整块的修改不会改变相对大小，因此总时间复杂度为 \(O(q\sqrt{n}\log \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
85
86
87
88
89
90
91
92
93
94
#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

void solve() {
    int n, q;
    cin >> n >> q;
    int sqn = sqrt(n);
    vector<int> st(sqn + 1), ed(sqn + 1), mark(sqn + 1), sz(sqn + 1);
    vector<vector<int>> v(sqn + 1);
    vector<int> a(n + 1), bel(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    for (int i = 1; i <= sqn; i++) {
        st[i] = n / sqn * (i - 1) + 1;
        ed[i] = n / sqn * i;
    }
    ed[sqn] = n;
    for (int i = 1; i <= sqn; i++) {
        for (int j = st[i]; j <= ed[i]; j++) {
            bel[j] = i;
            v[i].push_back(a[j]);
        }
        sort(v[i].begin(), v[i].end());
    }
    while (q--) {
        char op;
        int l, r, k;
        cin >> op >> l >> r >> k;
        if (op == 'M') {
            auto update = [&](int id) {
                int j = 0;
                for (int i = st[id]; i <= ed[id]; i++) {
                    v[id][j++] = a[i];
                }
                sort(v[id].begin(), v[id].end());
            };
            if (bel[l] == bel[r]) {
                for (int i = l; i <= r; i++) {
                    a[i] += k;
                }
                update(bel[l]);
            } else {
                for (int i = l; i <= ed[bel[l]]; i++) {
                    a[i] += k;
                }
                update(bel[l]);
                for (int i = st[bel[r]]; i <= r; i++) {
                    a[i] += k;
                }
                update(bel[r]);
                for (int i = bel[l] + 1; i < bel[r]; i++) {
                    mark[i] += k;
                }
            }
        } else {
            int cnt = 0;
            if (bel[l] == bel[r]) {
                for (int i = l; i <= r; i++) {
                    cnt += (mark[bel[i]] + a[i] >= k);
                }
            } else {
                for (int i = l; i <= ed[bel[l]]; i++) {
                    cnt += (mark[bel[i]] + a[i] >= k);
                }
                for (int i = st[bel[r]]; i <= r; i++) {
                    cnt += (mark[bel[i]] + a[i] >= k);
                }
                for (int i = bel[l] + 1; i < bel[r]; i++) {
                    cnt += (v[i].end() -
                            lower_bound(v[i].begin(), v[i].end(), k - mark[i]));
                }
            }
            cout << cnt << "\n";
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

莫队算法

莫队算法是使用了双指针的思想，并且通过分块的方法，使得序列上的区间查询问题，如果 \([l, r]\) 的答案能够拓展到 \([l-1,r],[l+1,r],[1,r-1],[l,r+1]\)，就能在 \(O(n\sqrt{n})\) 的复杂度离线求出所有询问的答案。

在上面给出的区间拓展的要求，双指针最基本的思想就是维护 \([l,r]\) 的答案，然后通过移动两个指针，动态更新范围内所需要的信息。我们很容易想到这样做的弊端——如果查询区间在 \([1,1]\) 和 \([n,n]\) 不断切换，每次查询的复杂度就是 \(O(n)\) 的，总共会达到 \(O(n^2)\)。为了避免这种情况，我们读取所有查询后，将查询范围按照 \(l\) 为第一关键字，\(r\) 为第二关键字进行排序，能起到一定程度的优化，而排序的操作也说明莫队是一个离线算法。

然而，这个优化并不显著，虽然排序后我们保证了左指针最多移动 \(n\) 次，但是考虑这样的询问：\([1,n], [2,2],[3,n],...\) 每一次询问右指针仍然会在两端大范围移动，最坏还是能达到 \(O(n^2)\) 的复杂度，还是不能使用。

此时，莫涛大神提出的莫队算法，基于分块，让上面的方法得到优化，最终成为了一种暴力但是剪枝极为巧妙的算法。

首先，基于分块，我们把数组分为 \(\sqrt{n}\) 个块，然后对查询区间进行排序，按照以下的规则：首先按照左端点所在序号排序，如果左端点所在块相同，就按右端点排序。这样的排序方法相比之前有什么不同？我们粗略地理解一下：这样的排序方法避免了上面右指针不停左右横跳的状况，每 \(\sqrt{n}\) 个数才可能大范围移动一次，我们感性地认为它是一个 \(O(n\sqrt{n})\) 的算法（更正确的证明在此处省略，可参照 OI-Wiki）。可见，仅仅是一个分块 + 排序算法，就让总复杂度降低了一个根号，不过这样的复杂度很多时候还是比较极限，需要搭配一些卡常的技巧。而且，莫队算法的实现上有很多细节，需要特别注意。

奇偶化排序

虽然按照上面的排序算法能降低一个根号的复杂度，我们最好还是能够通过一些方式降低常数，奇偶化排序就是一个很好的办法。

具体方式为：我们让左端点在同一奇数块的区间，右端点按照升序排列，反之降序。我们也是感性理解一下：这样排序，首先 \(r\) 在 0 位置，往右走到 \(n\) 时会处理完第一块询问，从 \(n\) 走到 1 时又会处理完第二块询问。而原来的排序方式，往右走到 \(n\) 时会处理完第一块询问，但是第二块询问要先走到 1，然后从 1 走到 \(n\) 才能处理。我们感性上理解，这样的排序方法能够让常数降低一些，比较玄学。

细节实现

在一些题目中，我们需要维护的是区间内数的种类数，例如，通过 set 来维护，如果处理不当指针的移动顺序，可能就会进行操作删除 set 内不存在的数而导致错误发生，因此，必须详细分析指针的含义。

由于我们的 \([l,r]\) 代表的是闭区间，因此，相当于右指针加入了 \([1,r]\) 的元素，而左指针删去了 \([1, l-1]\) 的元素，这样使得区间内元素正确，因此，我们作如下指针大小的讨论：

  • \(l\le r\)：此时完全正确，区间包含的就是 \([l,r]\)。
  • \(l = r + 1\)：此时相当于加入了 \([1,r]\) 的元素，又删去了 \([1,l-1]\) 即 \([1,r]\) 的元素，含义是没有任何元素在区间内，可以作为我们初始值。
  • \(l > r + 1\)：此时会有元素不被加入却被删去，我们需要避免这种情况。

因此，我们初始化时可以选择 \(l = 1, r = 0\)，代表区间没有元素，在移动区间时，尤其需要注意要先扩大区间（l--,r++），再减小区间（l++,r--），就能避免出现第三种情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
auto add = [&](int x) {
    if (cnt[x] == 0) {
        ans++;
    }
    cnt[x]++;
};
auto del = [&](int x) {
    cnt[x]--;
    if (cnt[x] == 0) {
        ans--;
    }
};
while (l > x) {
    add(a[--l]);
}
while (r < y) {
    add(a[++r]);
}
while (l < x) {
    del(a[l++]);
}
while (r > y) {
    del(a[r--]);
}

例题

[Luogu P1972 SDOI2009]HH的项链

HH 有一串由各种漂亮的贝壳组成的项链。HH 相信不同的贝壳会带来好运，所以每次散步完后，他都会随意取出一段贝壳，思考它们所表达的含义。HH 不断地收集新的贝壳，因此，他的项链变得越来越长。有一天，他突然提出了一个问题：某一段贝壳中，包含了多少种不同的贝壳？这个问题很难回答……因为项链实在是太长了。于是，他只好求助睿智的你，来解决这个问题。

题解

模版题，不过这题 \(n\) 是 1e6 的，会TLE。

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
#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

void solve() {
    int n;
    cin >> n;
    int sqn = sqrt(n);
    vector<int> a(n + 1), st(sqn + 1), ed(sqn + 1), bel(n + 1);
    vector<int> cnt(1000001);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= sqn; i++) {
        st[i] = n / sqn * (i - 1) + 1;
        ed[i] = n / sqn * i;
    }
  	ed[sqn] = n;
  	for (int i = 1; i <= sqn; i++) {
        for (int j = st[i]; j <= ed[i]; j++) {
            bel[j] = i;
        }
    }
    int q;
    cin >> q;
    vector<array<int, 3>> b(q);
    for (int i = 0; i < q; i++) {
        int x, y;
        cin >> x >> y;
        b[i] = {x, y, i};
    }
    sort(b.begin(), b.end(),
         [&](const array<int, 3> &a, const array<int, 3> &b) {
             if (bel[a[0]] == bel[b[0]]) {
                 return bel[a[0]] % 2 == 1 ? a[1] < b[1] : a[1] > b[1];
             }
             return a[0] < b[0];
         });
    int l = 1, r = 0;
    int ans = 0;
    vector<int> res(q);
    for (auto [x, y, i] : b) {
        auto add = [&](int x) {
            if (cnt[x] == 0) {
                ans++;
            }
            cnt[x]++;
        };
        auto del = [&](int x) {
            cnt[x]--;
            if (cnt[x] == 0) {
                ans--;
            }
        };
        while (l > x) {
            add(a[--l]);
        }
        while (r < y) {
            add(a[++r]);
        }
        while (l < x) {
            del(a[l++]);
        }
        while (r > y) {
            del(a[r--]);
        }
        res[i] = ans;
    }
    for (auto x : res) {
        cout << x << "\n";
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}