Skip to content

Mo's Algorithm with Updates

Please ensure you already understand the ordinary Mo's algorithm. If not, please read the previous section on Ordinary Mo's Algorithm first.

Features

The ordinary Mo's algorithm cannot handle modifications.

We can forcibly make it support modifications, similar to DP, by adding an extra time dimension representing the number of modifications experienced.

The time dimension indicates the number of modifications undergone.

That is, transform a query \([l,r]\) into \([l,r,\text{time}]\).

Then our coordinates can also move along the time dimension, meaning \([l,r,\text{time}]\) gains an extra direction to move, which 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]\)

Such transitions are also \(O(1)\), but we now have an additional keyword for sorting, which we need to handle accordingly.

We can use a method similar to ordinary Mo's algorithm for sorting and transitions, achieving \(O(n^{5/3})\).

This time, our sorting method divides the sequence into blocks of size \(n^{2/3}\), resulting in \(n^{1/3}\) blocks. The first keyword is the block index of the left endpoint, the second keyword is the block index of the right endpoint, and the third keyword is time.

Optimal Block Size and Time Complexity Analysis

Let the sequence length be \(n\), with \(m\) queries and \(t\) modifications.

The second keyword for sorting in Mo's algorithm with modifications is the block index of the right endpoint, which differs from ordinary Mo's algorithm.

Think about it: if we do not partition the right endpoint:

  • Disordered right endpoints would move \(n\) times for each query.
  • Ordered right endpoints would lead to disordered time, moving \(t\) times per query.

In either case, the resulting time overhead is unacceptable.

Next, we analyze the time complexity.

Let the block size be \(s\), then there are \(\dfrac{n}{s}\) blocks. For blocks \(i\) and \(j\), denote \(q_{i,j}\) as the number of queries whose left endpoint is in block \(i\) and right endpoint is in block \(j\).

For each "group" of queries \((i,j)\) where the left and right endpoints do not change blocks, the endpoints move \(O(s)\) times per query, and time increases monotonically, costing \(O(t)\).

The time for changing blocks of left and right endpoints is negligible.

This can be expressed as:

\[ \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 finding the derivative to determine the minimum of this expression. Let \(f(s)=ms+\dfrac{n^2t}{s^2}\). Then \(f'(s)=m-\dfrac{2n^2t}{s^3}=0\).

Solving gives \(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 size 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 mentioned \(O\left(n^{5/3}\right)\) assumes \(n,m,t\) are of the same order of magnitude.

In practice, it is still recommended to set the block size to \(n^{2/3}\).

Example

Example 「National Training Team」Color/Maintain Queue

Problem summary: You are given a sequence and \(M\) operations. There are two types of operations:

  1. Modify the number at a specific position in the sequence.
  2. Query the number of distinct numbers in the interval \([l,r]\) (multiple identical numbers count as one).

We can easily see that if operation 1 (modification) is not present, we can solve it using ordinary Mo's algorithm.

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

Process

First, consider the approach of ordinary Mo's algorithm:

  • When expanding the interval, for each number added, count how many times it has already appeared. If the count was \(0\) before adding, it means this is a new number, so increment the answer by \(1\). Then increment the occurrence count of this number by \(1\).
  • When shrinking the interval, for each number removed, count how many times it appears after removal. If the count becomes \(0\) after removal, it means this number has been completely removed from the current interval, i.e., the current interval loses one color, so decrement the answer by \(1\). Then decrement the occurrence count of this number by \(1\).

Now consider modifications:

  • Single-point modification: change the number at a specific position. Suppose we transition from a query that has undergone \(i\) modifications to a query that has undergone \(j\) modifications, and \(i<j\). Then we need to forcibly apply modifications \(i+1\) to \(j\).
  • If \(j<i\), then we need to forcibly revert modifications \(j+1\) to \(i\).

How do we forcibly apply a modification? Suppose a modification changes the color at position \(pos\) from \(a\) to \(b\), and assume the current Mo's interval has expanded to \([l,r]\).

  • Apply this modification: First, check if \(pos\) is within the interval \([l,r]\). If it is, we effectively remove color \(a\) from the interval and add color \(b\), and update the color at position \(pos\) in the current color sequence to \(b\). If it is not within \([l,r]\), we directly update the color at position \(pos\) in the current color sequence to \(b\).
  • Revert this modification: Equivalent to applying a modification that changes the color at position \(pos\) from \(b\) back to \(a\).

Thus, this problem is easily solved using Mo's algorithm with modifications!

Implementation

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#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';
  }
}
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用