Rollback Mo's Algorithm

Introduction

For some problems, it may be impossible to implement the addition or deletion operations during interval transitions. When only addition is impossible or only deletion is impossible, rollback Mo's algorithm can solve the problem in \(O(n \sqrt m)\) time. The core idea of rollback Mo's algorithm is: since only one operation can be implemented, then only use that one operation, and leave the rest to rollback.

Rollback Mo's algorithm is divided into two types: one that only uses addition operations and one that only uses deletion operations. Only the rollback Mo's algorithm that uses only addition operations is introduced below. The rollback Mo's algorithm that uses only deletion operations differs only slightly in implementation, so it will not be elaborated further.

Example Problem JOISC 2014 Day1 Historical Research

You are given an array \(A\) of length \(n\) and \(m\) queries \((1 \leq n, m \leq 10^5)\). Each query asks for the number with the greatest importance in the interval \([L, R]\), requiring outputting its importance. The importance of a number \(i\) is defined as \(i\) multiplied by the number of times \(i\) appears in the interval.

In this problem, updating the answer during addition is easy to implement, but updating the answer during deletion is difficult. This is because if addition affects the answer, the new answer must be the importance of the number just added. However, if the number with the greatest importance changes after deletion, it is hard to determine which number becomes the new most important one. Therefore, ordinary Mo's algorithm struggles with this problem.

Process

Partition the original sequence into blocks. Sort the queries in ascending order of the block index of the left endpoint as the first key, and ascending order of the right endpoint as the second key.
Process the queries in order:
- If the block \(B\) of the query's left endpoint differs from that of the previous query, initialize the left endpoint of the Mo's interval to \(B\)'s right endpoint plus \(1\), and initialize the right endpoint of the Mo's interval to \(B\)'s right endpoint;
- If the left and right endpoints of the query belong to the same block, directly scan the interval to answer the query;
- If the left and right endpoints of the query belong to different blocks:
  - If the query's right endpoint is greater than the Mo's interval's right endpoint, continuously expand the right endpoint until the Mo's interval's right endpoint equals the query's right endpoint;
  - Continuously expand the Mo's interval's left endpoint until it equals the query's left endpoint;
  - Answer the query;
  - Undo the changes to the left endpoint of the Mo's interval, rolling back the left endpoint to \(B\)'s right endpoint plus \(1\).

Complexity Proof

Assume the block size of rollback Mo's algorithm is \(b\):

For queries where the left and right endpoints are in the same block, they can be computed in \(O(b)\) time;
For other queries, consider queries whose left endpoints are in the same block. Their right endpoints increase monotonically, so moving the right endpoint has a time complexity of \(O(n)\). The left endpoint moves at most \(b\) per query. Since there are \(\frac{n}{b}\) blocks, the total complexity is \(O(mb+\frac{n^2}{b})\). Setting \(b=\frac{n}{\sqrt{m}}\) gives the optimal time complexity of \(O(n\sqrt{m})\).

Implementation

Reference Code

#include <algorithm>
#include <cmath>
#include <iostream>
using namespace std;
using ll = long long;
constexpr int N = 1e5 + 5;
int n, q;
int x[N], t[N], m;

struct Query {
  int l, r, id;
} Q[N];

int pos[N], L[N], R[N], sz, tot;
int cnt[N], __cnt[N];
ll ans[N];

bool cmp(const Query& A, const Query& B) {
  if (pos[A.l] == pos[B.l]) return A.r < B.r;
  return pos[A.l] < pos[B.l];
}

void build() {
  sz = sqrt(n);
  tot = n / sz;
  for (int i = 1; i <= tot; i++) {
    L[i] = (i - 1) * sz + 1;
    R[i] = i * sz;
  }
  if (R[tot] < n) {
    ++tot;
    L[tot] = R[tot - 1] + 1;
    R[tot] = n;
  }
}

void Add(int v, ll& Ans) {
  ++cnt[v];
  Ans = max(Ans, 1LL * cnt[v] * t[v]);
}

void Del(int v) { --cnt[v]; }

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n >> q;
  for (int i = 1; i <= n; i++) cin >> x[i], t[++m] = x[i];
  for (int i = 1; i <= q; i++) cin >> Q[i].l >> Q[i].r, Q[i].id = i;

  build();

  // Sort the queries
  for (int i = 1; i <= tot; i++)
    for (int j = L[i]; j <= R[i]; j++) pos[j] = i;
  sort(Q + 1, Q + 1 + q, cmp);

  // Discretization
  sort(t + 1, t + 1 + m);
  m = unique(t + 1, t + 1 + m) - (t + 1);
  for (int i = 1; i <= n; i++) x[i] = lower_bound(t + 1, t + 1 + m, x[i]) - t;

  int l = 1, r = 0, last_block = 0, __l;
  ll Ans = 0, tmp;
  for (int i = 1; i <= q; i++) {
    // If the left and right endpoints of the query belong to the same block, answer by brute force scanning
    if (pos[Q[i].l] == pos[Q[i].r]) {
      for (int j = Q[i].l; j <= Q[i].r; j++) ++__cnt[x[j]];
      for (int j = Q[i].l; j <= Q[i].r; j++)
        ans[Q[i].id] = max(ans[Q[i].id], 1LL * t[x[j]] * __cnt[x[j]]);
      for (int j = Q[i].l; j <= Q[i].r; j++) --__cnt[x[j]];
      continue;
    }

    // If a new block is accessed, reinitialize the Mo's algorithm interval
    if (pos[Q[i].l] != last_block) {
      while (r > R[pos[Q[i].l]]) Del(x[r]), --r;
      while (l < R[pos[Q[i].l]] + 1) Del(x[l]), ++l;
      Ans = 0;
      last_block = pos[Q[i].l];
    }

    // Extend the right endpoint
    while (r < Q[i].r) ++r, Add(x[r], Ans);
    __l = l;
    tmp = Ans;

    // Extend the left endpoint
    while (__l > Q[i].l) --__l, Add(x[__l], tmp);
    ans[Q[i].id] = tmp;

    // Rollback
    while (__l < l) Del(x[__l]), ++__l;
  }
  for (int i = 1; i <= q; i++) cout << ans[i] << '\n';
  return 0;
}

References

Rollback Mo's Algorithm and Its Simple Applications | Parsnip's Blog

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