Skip to content

Mo's Algorithm with bitset

bitset is often used for decision and counting problems that are difficult to maintain with conventional data structures, while Mo's algorithm can maintain interval information that is hard to handle with regular data structures. Combining the two allows leveraging the advantages of both.

Example 「Ynoi2016」Falling into the Rabbit Hole

This problem fits the characteristics of combining Mo's algorithm with bitset as mentioned above. It is natural to think of using bitset to store all distinct values that appear in each interval. The answer for a set of queries is the sum of the lengths of all intervals minus the number of elements in the union of the three sets multiplied by \(3\).

However, when using bitset with Mo's algorithm, adjustments must be made to account for the features of bitset:

  1. bitset does not handle multiple occurrences of the same value well. We can insert into the bitset the discretized value of the current element plus the current count of its occurrences in the interval.
  2. When using Mo's algorithm, we might not pay attention to the order of the four pointer movement methods, which can lead to situations where the left pointer is to the right of the right pointer, resulting in a negative interval length and thus a negative count of elements. This usually doesn't matter in other cases, but in this problem, the elements inserted into the bitset depend on the count, so we must be careful about the order of the four pointer movements. We should write the statements that move the left and right pointers to the left and right first to avoid inserting negative numbers into the bitset.
  3. Although bitset uses little space, it still struggles with data of size \(10 ^ 5 \times 10 ^ 5\). Therefore, we need to split the queries into constant-sized blocks and process them separately, ensuring that the space usage is just enough while keeping the time complexity unchanged.
Reference Code 
 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
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstring>
#include <iostream>
using namespace std;
constexpr int N = 100005, M = N / 3 + 10;
int n, m, maxn;
int a[N], ans[M], cnt[N];
bitset<N> sum[M], now;

struct query {
  int l, r, id;

  bool operator<(const query& x) const {
    if (l / maxn != x.l / maxn) return l < x.l;
    return (l / maxn) & 1 ? r < x.r : r > x.r;
  }
} q[M * 3];

void static_set() {
  static int tmp[N];
  memcpy(tmp, a, sizeof(a));
  sort(tmp + 1, tmp + n + 1);
  for (int i = 1; i <= n; i++)
    a[i] = lower_bound(tmp + 1, tmp + n + 1, a[i]) - tmp;
}

void add(int x) {
  now.set(x + cnt[x]);
  cnt[x]++;
}

void del(int x) {
  cnt[x]--;
  now.reset(x + cnt[x]);
}

void solve() {
  int cnt = 0, tot = 0;
  now.reset();
  for (tot = 0; tot < M - 5 && m; tot++) {
    m--;
    ans[tot] = 0;
    sum[tot].set();
    for (int j = 0; j < 3; j++) {
      cin >> q[cnt].l >> q[cnt].r;
      q[cnt].id = tot;
      ans[tot] += q[cnt].r - q[cnt].l + 1;
      cnt++;
    }
  }
  sort(q, q + cnt);
  for (int i = 0, l = 1, r = 0; i < cnt; i++) {
    while (l > q[i].l) add(a[--l]);
    while (r < q[i].r) add(a[++r]);
    while (l < q[i].l) del(a[l++]);
    while (r > q[i].r) del(a[r--]);
    sum[q[i].id] &= now;
  }
  for (int i = 0; i < tot; i++)
    cout << ans[i] - (int)sum[i].count() * 3 << '\n';
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n >> m;
  for (int i = 1; i <= n; i++) cin >> a[i];
  static_set();
  maxn = sqrt(n);
  solve();
  memset(cnt, 0, sizeof(cnt));
  solve();
  memset(cnt, 0, sizeof(cnt));
  solve();
  return 0;
}

Exercises

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用