AIOJ

Bitsets are often used for decision and counting problems that are difficult to maintain with ordinary data structures, while Mo's algorithm can maintain interval information that ordinary data structures find difficult to handle. Combining the two allows us to take advantage of both.

Example problem “Ynoi2016” Fallen into a Rabbit Hole

This problem fits the characteristics of combining Mo's algorithm with bitsets described above. It is not difficult to see that we can use a bitset to store all values that occur in each interval. The answer to a group of queries is the sum of the lengths of all intervals minus the number of elements in the union of the three sets $\times 3$ .

However, using bitsets with Mo's algorithm also requires adapting the algorithm to the characteristics of bitsets:

A bitset cannot handle the case where multiple occurrences of the same value appear very well. We can use the sum of the discretized value of the current element and its current frequency in the interval as the object inserted into the bitset.
When using Mo's algorithm, we may not pay attention to the order of the four ways of moving the pointers. During pointer movement, the left endpoint may end up to the right of the right endpoint, making the interval length negative and consequently making the number of elements negative. This has no effect in other situations, but in this problem the elements inserted into the bitset depend on the element counts. Therefore, we need to pay attention to the order of the four pointer movements and put the statements that move the left and right pointers outward first, avoiding inserting negative numbers into the bitset.
Although bitsets use little space, they still cannot handle a data scale of $10 ^ 5 \times 10 ^ 5$ . Therefore, we need to divide the queries into a constant number of blocks and process them separately, keeping the time complexity unchanged while ensuring that the space is just sufficient.

Reference code

#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;
}

Mo's Algorithm with Bitsets

Example problem “Ynoi2016” Fallen into a Rabbit Hole

Exercises