AIOJ

Please make sure that you already know ordinary Mo's algorithm. If you do not, read the earlier ordinary Mo's algorithm first.

Features

Ordinary Mo's algorithm cannot handle modifications.

We can force it to support modifications, just as with DP, by adding a time dimension to represent the time of this operation.

The time dimension represents the number of modifications that have been applied.

That is, turn a query $[l,r]$ into $[l,r,\text{time}]$ .

Our position can also move along the time dimension. The state $[l,r,\text{time}]$ has one additional movable direction and can become:

$[l-1,r,\text{time}]$
$[l+1,r,\text{time}]$
$[l,r-1,\text{time}]$
$[l,r+1,\text{time}]$
$[l,r,\text{time}-1]$
$[l,r,\text{time}+1]$

These transitions also take $O(1)$ time, but sorting has one more key; it only needs to be handled appropriately.

We can sort and transition using a method similar to ordinary Mo's algorithm, achieving $O(n^{5/3})$ .

This time, we sort using blocks of size $n^{2/3}$ , divided into $n^{1/3}$ blocks. The first key is the block containing the left endpoint, the second key is the block containing the right endpoint, and the third key is time.

Optimal block length and time-complexity analysis

Let the sequence length be $n$ , with $m$ queries and $t$ modifications.

The second key when sorting Mo's algorithm with modifications is the block number containing the right endpoint, unlike ordinary Mo's algorithm.

Think about what happens if the right endpoint is not divided into blocks:

An unordered right endpoint moves $n$ times for every query.
An ordered right endpoint results in unordered time, so it moves $t$ times for every query.

Neither case has an acceptable time cost.

Next, analyze the time complexity.

Let the block length be $s$ , so there are $\dfrac{n}{s}$ blocks. For blocks $i$ and $j$ , let $q_{i,j}$ be the number of queries whose left endpoint lies in block $i$ and whose right endpoint lies in block $j$ .

For each “group” of queries $(i,j)$ whose endpoints do not change blocks, each endpoint moves $O(s)$ times, while time increases monotonically, costing $O(t)$ .

Ignore the time spent changing the blocks of the left and right endpoints.

In other words:

\begin{aligned} &\sum_{i=1}^{n/s}\sum_{j=i+1}^{n/s}(q_{i,j}\cdot s+t)\\ =&ms+\left(\dfrac{n}{s}\right)^2t\\ =&ms+\dfrac{n^2t}{s^2} \end{aligned}

Consider differentiating to find the minimum of this expression. Let $f(s)=ms+\dfrac{n^2t}{s^2}$ . Then $f'(s)=m-\dfrac{2n^2t}{s^3}=0$ .

We obtain $s=\sqrt[3]{\dfrac{2n^2t}{m}}=\dfrac{2^{1/3}n^{2/3}t^{1/3}}{m^{1/3}}=s_0$ .

That is, when the block length is $\dfrac{n^{2/3}t^{1/3}}{m^{1/3}}$ , the optimal time complexity is $O\left(n^{2/3}m^{2/3}t^{1/3}\right)$ .

The commonly stated $O\left(n^{5/3}\right)$ is the time complexity obtained by treating $n,m,t$ as being of the same order of magnitude.

In practice, it is still recommended to set the block length to $n^{2/3}$ .

Example problem

Example problem: “National Training Team” Counting Colors / Maintaining a Queue

Problem summary: Given a sequence and M operations, there are two types of operations:

Modify the number at one position in the sequence.
Query the number of distinct numbers in the interval $[l,r]$ (multiple equal numbers count only once).

It is not difficult to see that, without operation 1 (modification), ordinary Mo's algorithm can solve the problem easily.

However, the problem also includes point modifications, so we use Mo's algorithm with modifications.

Process

First consider the ordinary Mo's algorithm:

Each time the interval is expanded, when a number is added, count how many times it has already appeared. If its count before insertion is $0$ , this means it is a new number, so the answer increases by $+1$ . Then increase this number's count by $+1$ .
Each time the interval is reduced, when a number is deleted, count how many times it appears after deletion. If its count after deletion is $0$ , this means that the number has been completely removed from the current interval; in other words, the current interval has lost one color, so the answer decreases by $-1$ . Then decrease this number's count by $-1$ .

Now consider modifications:

A point modification changes the number at one position. Suppose we move from a query that has experienced $i$ modifications to a query that has experienced $j$ modifications, with $i<j$ ; then we need to forcibly apply modifications $i+1$ through $j$ .
Suppose $j [!note]- Reference code

#include <algorithm>
#include <cmath>
#include <iostream>
using namespace std;

long long qsize;

struct query {
  long long id, t, l, r;

  bool operator<(query b) const {
    if (l / qsize != b.l / qsize) {
      return l / qsize > b.l / qsize;
    } else if (r / qsize != b.r / qsize) {
      return r / qsize > b.r / qsize;
    } else {
      return t > b.t;
    }
  }
} q[150009];

struct operation {
  long long p, x;
} r[150009];

char op;
long long n, m, x, y, cur, qcnt, rcnt, mp[1500009], a[150009], ans[150009];

void add(long long x) {
  if (!mp[x]) {
    cur += 1;
  }
  mp[x] += 1;
}

void del(long long x) {
  mp[x] -= 1;
  if (!mp[x]) {
    cur -= 1;
  }
}

void process() {
  sort(q + 1, q + qcnt + 1);
  long long L = 1, R = 0, last = 0;
  for (long long i = 1; i <= qcnt; i++) {
    while (R < q[i].r) {
      add(a[++R]);
    }
    while (R > q[i].r) {
      del(a[R--]);
    }
    while (L > q[i].l) {
      add(a[--L]);
    }
    while (L < q[i].l) {
      del(a[L++]);
    }
    while (last < q[i].t) {
      last += 1;
      if (r[last].p >= L && r[last].p <= R) {
        add(r[last].x);
        del(a[r[last].p]);
      }
      swap(a[r[last].p], r[last].x);
    }
    while (last > q[i].t) {
      if (r[last].p >= L && r[last].p <= R) {
        add(r[last].x);
        del(a[r[last].p]);
      }
      swap(a[r[last].p], r[last].x);
      last -= 1;
    }
    ans[q[i].id] = cur;
  }
}

signed main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  cin >> n >> m;
  qsize = pow(n, 2.0 / 3.0);
  for (long long i = 1; i <= n; i++) {
    cin >> a[i];
  }
  for (long long i = 1; i <= m; i++) {
    cin >> op >> x >> y;
    if (op == 'Q') {
      ++qcnt, q[qcnt] = {qcnt, rcnt, x, y};
    } else if (op == 'R') {
      r[++rcnt] = {x, y};
    }
  }
  process();
  for (long long i = 1; i <= qcnt; i++) {
    cout << ans[i] << '\n';
  }
}

Mo's Algorithm with Modifications

Features

Example problem

Process