AIOJ

Introduction

Some problems make one of the two interval operations—adding an element or removing an element—difficult to implement during interval transitions. When only additions or only removals are difficult, rollback Mo's algorithm can solve the problem in $O(n \sqrt m)$ . Its central idea is: if only one operation is easy to implement, use only that operation and let rollback handle the other one.

Rollback Mo's algorithm has an add-only version and a delete-only version. The add-only version is described below. The delete-only version differs only slightly in implementation, so it is omitted.

Example: JOISC 2014 Day1 Historical Research

You are given an array $n$ of length $A$ and $m$ queries $(1 \leq n, m \leq 10^5)$ . For each interval $[L, R]$ , find the number with the greatest importance, and output its importance. The importance of a number $i$ is defined as $i$ multiplied by the number of times $i$ occurs in the interval.

In this problem, updating the answer while adding an element is easy, but updating it while removing an element is difficult. If an addition changes the answer, the new answer must be the importance of the newly added number. If removing an element changes the most important number in the interval, it is hard to determine which number is now the most important. Thus ordinary Mo's algorithm has difficulty solving this problem.

Process

Divide the original sequence into blocks. Sort queries by the block number containing their left endpoint as the primary key and by increasing right endpoint as the secondary key.
Process the queries in order:
- If the block $B$ containing the current query's left endpoint differs from that of the previous query, initialize the Mo interval's left endpoint to the right endpoint of $B$ plus $1$ , and its right endpoint to the right endpoint of $B$ .
- If the query's two endpoints lie in the same block, scan the interval directly and answer it.
- Otherwise:
  - If the query's right endpoint is greater than the Mo interval's right endpoint, repeatedly extend the right endpoint until it reaches the query's right endpoint.
  - Repeatedly extend the Mo interval's left endpoint leftward until it reaches the query's left endpoint.
  - Answer the query.
  - Undo the changes to the Mo interval's left endpoint, rolling it back to the right endpoint of $B$ plus $1$ .

Complexity proof

Suppose the rollback Mo block size is $b$ :

A query whose endpoints lie in the same block can be computed in $O(b)$ time.
For the other queries, consider queries whose left endpoints lie in the same block. Their right endpoints increase monotonically, so moving the right endpoint costs $O(n)$ , while moving the left endpoint costs at most $b$ per query. Since there are $\frac{n}{b}$ blocks, the total complexity is $O(mb+\frac{n^2}{b})$ . Taking $b=\frac{n}{\sqrt{m}}$ minimizes this expression, giving a 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);

  // Discretize
  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++) {
    // Answer directly by brute force if both endpoints are in one block
    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;
    }

    // Reinitialize the Mo interval when entering a new block
    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;

    // Roll back
    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 a simple application | Parsnip's Blog