莫队算法

最后更新于：2022年6月25日 下午

首先莫队算法是一个离散算法，复杂度 \(O(n \sqrt{m})\) 一般用于 \(m\) 次长为 \(n\) 的区间问题

普通莫队

首先按照左端点所在的块为第一关键字，再按照右端点升序为第二关键字排序。优化：如果都是从小到大，那么由于这样两个指标都是上升的（就会来来回回好几次），因此我们可以奇偶交替排序，即奇数块从小到大排序，偶数快从大到小排序

但是我们可以心中有分块，但是代码中不表现出来！（例如 OI-wiki 中示例代码），但是示例代码的做法不可避免的牵扯到除法，那还不如按照原始做法来，但是注意依然心中有块即可。

注意四个循环的位置，遵寻先放大区间再缩小区间的策略即可，先动做还是先动右无区别。

注意到 stl 排序中必须要保证 \(a < b\) 和 \(b < a\) 最多一个成立

模板例题：LOJ 1494 的优雅做法（这里 sn 可取 \(\frac{n}{\sqrt{m}}\)：

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
#include <bits/stdc++.h>
#define watch(x) std::cout << (#x) << " is " << (x) << std::endl
using LL = long long;

struct Node {
  int l, r, id, b;
  bool operator<(const Node & A) const {
    if (b != A.b) return l < A.l;
    if (b & 1) return r < A.r;
    return r > A.r;
  }
};

int main() {
  //freopen("in", "r", stdin);
  std::cin.tie(nullptr)->sync_with_stdio(false);
  int n, m;
  std::cin >> n >> m;
  std::vector<int> a(n);
  for (auto &x : a) std::cin >> x;
  int sn = n / std::sqrt(m);
  std::vector<Node> b(m);
  for (int i = 0; i < m; ++i) {
    std::cin >> b[i].l >> b[i].r;
    --b[i].l; --b[i].r;
    b[i].b = b[i].l / sn;
    b[i].id = i;
  }
  std::sort(b.begin(), b.end());
  LL cur = 0;
  std::vector<int> cnt(n + 1);
  auto add = [&](int x) {
    cur += cnt[x];
    ++cnt[x];
  };
  auto del = [&](int x) {
    --cnt[x];
    cur -= cnt[x];
  };
  std::vector<LL> f(n), g(n);
  int l = 0, r = -1;
  for (int i = 0; i < m; ++i) {
    if (b[i].l == b[i].r) {
      f[b[i].id] = 0, g[b[i].id] = 1;
    } else {
      while (l > b[i].l) add(a[--l]);
      while (r < b[i].r) add(a[++r]);
      while (l < b[i].l) del(a[l++]);
      while (r > b[i].r) del(a[r--]);
      f[b[i].id] = cur;
      g[b[i].id] = LL(r - l + 1) * (r - l) / 2;
    }
  }
  for (int i = 0; i < m; ++i) {
    if (f[i]) {
      LL d = std::__gcd(f[i], g[i]);
      f[i] /= d; g[i] /= d;
    } else g[i] = 1;
    std::cout << f[i] << '/' << g[i] << '\n';
  }
  return 0;
}

带修改的莫队能做到 \(O(n^{\frac{5}{3}})\)，没啥学的兴趣了。树上莫队就是把树结构转化成线性结构

回滚莫队

例题：LibreOJ-2874 的提交，如果用普通莫队的话，利用优先队列和 map 来加减操作会多加一个 log。因此我们这里使用回滚莫队。

回滚莫队的策略就是：如果需要考虑的左右端点在同一个块中，那么我们就直接暴力求解，这一类区间总复杂度不会超过 \(O(n \sqrt{n}\)，这样分情况是为了能够做回滚，即让 l 在块的右端点，r 初始在块的右端点， l 在 r 右边挨着，然后始终保持 r 右移，l 左移动.

这里不用上面的奇偶优化，是因为这里真的要分块解决。不得不说我的代码写的真的优雅

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
#include <bits/stdc++.h>
#define watch(x) std::cout << (#x) << " is " << (x) << std::endl
using LL = long long;

template<typename T>
std::vector<T> discrete(std::vector<T>& a) {
  auto b = a;
  std::sort(b.begin(), b.end());
  b.erase(std::unique(b.begin(), b.end()), b.end());
  std::vector<T> r(b.size());
  for (auto & x : a) {
    int id = std::lower_bound(b.begin(), b.end(), x) - b.begin();
    r[id] = x;
    x = id;
  }
  return r;
}

struct Node {
  int l, r, id, b;
  // 同一个块按照右端点排列，不同块按照左端点排列
  bool operator<(const Node & A) const {
    if (b != A.b) return l < A.l;
    return r < A.r;
  }
};

int main() {
  // freopen("in", "r", stdin);
  std::cin.tie(nullptr)->sync_with_stdio(false);
  int n, m;
  std::cin >> n >> m;
  std::vector<int> a(n);
  for (auto &x : a) std::cin >> x;
  auto c = discrete(a); // 数据范围需要离散化一下。
  int sn = n / std::sqrt(m) + 1; // 防止 sn 为 0，所以 + 1
  std::vector<Node> b(m);
  for (int i = 0; i < m; ++i) {
    std::cin >> b[i].l >> b[i].r;
    --b[i].l; --b[i].r;
    b[i].b = b[i].l / sn;
    b[i].id = i;
  }
  std::sort(b.begin(), b.end());
  std::vector<int> cnt(c.size()), tmpcnt(c.size());
  auto add = [&](int x, LL &now) {
    ++cnt[x];
    now = std::max(now, LL(c[x]) * cnt[x]);
  };
  auto del = [&](int x) {
    --cnt[x];
  };
  std::vector<LL> ans(m);
  LL cur = 0, tmp = 0;
  for (int i = 0, l = 0, r = -1, lastB = -1; i < m; ++i) {
    if (b[i].b != lastB) {
      // 对于新的块，初始化让 r 有这个块的右端点, l 是再右边一个
      int BL = std::min((b[i].b + 1) * sn, n) - 1;
      while (r < BL) add(a[++r], cur);
      while (r > BL) del(a[r--]);
      while (l <= BL) del(a[l++]);
      cur = 0;
      lastB = b[i].b;
    }
    if (l > b[i].r) { // 左右端点在同一块的，直接暴力
      for (int j = b[i].l; j <= b[i].r; ++j) ++tmpcnt[a[j]];
      for (int j = b[i].l; j <= b[i].r; ++j) {
        ans[b[i].id] = std::max(ans[b[i].id], LL(c[a[j]]) * tmpcnt[a[j]]);
      }
      for (int j = b[i].l; j <= b[i].r; ++j) --tmpcnt[a[j]];
    } else { // 剩下要求得，b[i].r 必然不在这个块中，即必然较大
      while (r < b[i].r) add(a[++r], cur);
      tmp = cur;
      int nl = l;
      while (nl > b[i].l) add(a[--nl], tmp);
      ans[b[i].id] = tmp;
      while (nl < l) del(a[nl++]);
    }
  }
  for (auto x : ans) std::cout << x << '\n';
  return 0;
}

学完回滚莫队才感觉真的懂了莫队的思想

学习莫队的动力例题：1514D

只需找到区间众数即可。

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
#include <bits/stdc++.h>
#define watch(x) std::cout << (#x) << " is " << (x) << std::endl
using LL = long long;

struct Node {
  int l, r, id, b;
  // 同一个块按照右端点排列，不同块按照左端点排列
  bool operator<(const Node & A) const {
    if (b != A.b) return l < A.l;
    return r < A.r;
  }
};

int main() {
  // freopen("in", "r", stdin);
  std::cin.tie(nullptr)->sync_with_stdio(false);
  int n, m;
  std::cin >> n >> m;
  std::vector<int> a(n);
  for (auto &x : a) std::cin >> x;
  int sn = n / std::sqrt(m) + 1; // 防止 sn 为 0，所以 + 1
  std::vector<Node> b(m);
  for (int i = 0; i < m; ++i) {
    std::cin >> b[i].l >> b[i].r;
    --b[i].l; --b[i].r;
    b[i].b = b[i].l / sn;
    b[i].id = i;
  }
  std::sort(b.begin(), b.end());
  std::vector<int> cnt(n + 1), tmpcnt(n + 1);
  auto add = [&](int x, int &now) {
    now = std::max(now, ++cnt[x]);
  };
  auto del = [&](int x) {
    --cnt[x];
  };
  std::vector<int> ans(m);
  int cur = 0;
  for (int i = 0, l = 0, r = -1, lastB = -1; i < m; ++i) {
    if (b[i].b != lastB) {
      // 对于新的块，初始化让 r 有这个块的右端点, l 是再右边一个
      int BL = std::min((b[i].b + 1) * sn, n) - 1;
      while (r < BL) add(a[++r], cur);
      while (r > BL) del(a[r--]);
      while (l <= BL) del(a[l++]);
      cur = 0;
      lastB = b[i].b;
    }
    if (l > b[i].r) { // 左右端点在同一块的，直接暴力
      for (int j = b[i].l; j <= b[i].r; ++j) {
        ans[b[i].id] = std::max(ans[b[i].id], ++tmpcnt[a[j]]);
      }
      for (int j = b[i].l; j <= b[i].r; ++j) --tmpcnt[a[j]];
    } else { // 剩下要求得，b[i].r 必然不在这个块中，即必然较大
      while (r < b[i].r) add(a[++r], cur);
      int tmp = cur, nl = l;
      while (nl > b[i].l) add(a[--nl], tmp);
      ans[b[i].id] = tmp;
      while (nl < l) del(a[nl++]);
    }
    ans[b[i].id] = std::max(1, 2 * ans[b[i].id] - (b[i].r - b[i].l + 1));
  }
  for (auto x : ans) std::cout << x << '\n';
  return 0;
}

后来遇到的莫队问题

  • P4137：普通莫队会被特殊数据 gank，带 log 的普通莫队也会被随机数据卡掉。因此只能用回滚莫队啦，并且是删除版本的回滚莫队！这里删除版本不用分情况讨论。提交记录