Mo's algorithm

Formulation

Suppose $n=m$. For range queries on a sequence, if the answer for $[l,r]$ can be extended in $O(1)$ time to the answers for $[l-1,r],[l+1,r],[l,r+1],[l,r-1]$ (the ranges adjacent to $[l,r]$), then all queries can be answered in $O(n\sqrt{n})$ time.

Explanation

After sorting offline, process the queries in order and brute-force transfer the answer from the previous range to the next (moving one step at a time).

Sorting method

For a range $[l,r]$, sort by the index of the block containing $l$ as the first key and by $r$ in ascending order as the second key.

Implementation

void move(int pos, int sign) {
  // update nowAns
}

void solve() {
  BLOCK_SIZE = int(ceil(pow(n, 0.5)));
  sort(querys, querys + m);
  for (int i = 0; i < m; ++i) {
    const query &q = querys[i];
    while (l > q.l) move(--l, 1);
    while (r < q.r) move(++r, 1);
    while (l < q.l) move(l++, -1);
    while (r > q.r) move(r--, -1);
    ans[q.id] = nowAns;
  }
}

Complexity analysis

The following discussion assumes that $n$ and $m$ are of the same order.

First comes block decomposition, whose time complexity is $O(\sqrt{n}\cdot\sqrt{n}\log\sqrt{n}+n\log n)=O(n\log n)$.

Next comes the essence of Mo's algorithm. We use an elementary proof below to show that its time complexity is $O(n\sqrt{n})$.

Therefore, the time complexity of Mo's algorithm is $O(n\sqrt{n})$.

For other values of $m$, such as $m<n$, the block decomposition must be changed for better performance.

How should we choose the blocks?

Let the block length be $S$. For any number of queries in the same block, the movement distance is $n$. There are $\displaystyle \frac{n}{S}$ blocks, so the total movement is $\displaystyle \frac{n^2}{S}$. Since movement may cross block boundaries, we must also add a complexity of $mS$. Thus, the total complexity is $\displaystyle O\left(\frac{n^2}{S}+mS\right)$. To minimize this value, the two terms should be made as equal as possible. We find that choosing $S$ as $\displaystyle \frac{n}{\sqrt{m}}$ is optimal, giving a complexity of $\displaystyle O\left(\frac{n^2}{\displaystyle \frac{n}{\sqrt{m}}}+m\left(\frac{n}{\sqrt{m}}\right)\right)=O(n\sqrt{m})$.

In fact, an inaccurate block length can greatly affect Mo's time complexity. For example, if $m$ and $\sqrt n$ are of the same order but the block length is incorrectly set to $\sqrt n$, it is easy to construct data with time complexity $O(n \sqrt n)$ instead of the correct $O(n^{5/4})$.

Mo's algorithm looks very brute-force largely because its block-sorting method looks rough. One might try a more refined sort of all ranges. For example, regard every range $[l, r]$ as a point $(l, r)$ in the plane, build a Manhattan minimum spanning tree on all points, and transfer answers between queries along its edges. This seems to improve the time complexity, but the upper bound of block-sorting the queries is already optimal.

Suppose $n, m$ are of the same order and $n$ is a perfect square. Consider ranges of the form $[a \sqrt n, b \sqrt n](1 \le a, b \le \sqrt n)$; there are $n$ such ranges. If all ranges are viewed as points in the plane, the Manhattan distance between two points is exactly the cost of transferring between the two ranges, and the minimum Manhattan distance between any two ranges is $\sqrt n$. Thus the minimum time complexity for processing all queries is $O(n \sqrt n)$. Other cases can be constructed similarly.

Mo's algorithm has another feature: with $n$ fixed, the larger $m$ is, the smaller the average transfer cost per query. Some other offline algorithms have the same feature (such as Tarjan's algorithm for finding LCAs), but Mo's algorithm shows the most pronounced change in average transfer cost as $m$ varies.

Example & code

Process

Idea: this is a template problem for Mo's algorithm.

For a range $[l,r]$, sort by the index of the block containing $l$ as the first key and by $r$ in ascending order as the second key.

Start calculating from the first query. Compute the first query by brute force in $O(n)$ time, then obtain each later answer from the previous query.

Details:

For the range $[i,i]$, the answer is easy because it contains only one element. Then move step by step from the current range, whose answer is known, toward the next range.

Let $col[i]$ denote the number of occurrences of color $i$ in the current range, and let $ans$ denote the number of valid pairs (the number of ways to choose two socks of the same color). On each move, update the answer: let the current color be $k$; when extending the range, add to $ans$ the value $\dbinom{col[k]+1}{2}-\dbinom{col[k]}{2}$; when shrinking, subtract from $ans$ the value $\dbinom{col[k]}{2}-\dbinom{col[k]-1}{2}$. The answer to this query is $\displaystyle \frac{ans}{\dbinom{r-l+1}{2}}$.

There is a simplification:$\displaystyle \dbinom{a}{2}=\frac{a (a-1)}{2}$．

Thus $\displaystyle \dbinom{a+1}{2}-\dbinom{a}{2}=\frac{(a+1) a}{2}-\frac{a (a-1)}{2}=\frac{a}{2}\cdot (a+1-a+1)=\frac{a}{2}\cdot 2=a$．

Thus $\dbinom{col[k]+1}{2}-\dbinom{col[k]}{2}=col[k]$．

Total complexity: $O(n\sqrt{n} )$

In the code below, deno is the denominator, nume is the numerator, sqn is the block size $\sqrt{n}$, arr is the input array, node is the query structure, tab is the sorted query sequence, and col is as defined above.

Note: because of ++l and --r, the positions of the four while loops that move the range in the following code are crucial; their relative order must not be changed arbitrarily.

Implementation

#include <algorithm>
#include <cmath>
#include <iostream>
using namespace std;
constexpr int N = 50005;
int n, m, maxn;
int c[N];
long long sum;
int cnt[N];
long long ans1[N], ans2[N];

struct query {
  int l, r, id;

  bool operator<(const query &x) const {  // Overload the < operator
    if (l / maxn != x.l / maxn) return l < x.l;
    return (l / maxn) & 1 ? r < x.r : r > x.r;
  }
} a[N];

void add(int i) {
  sum += cnt[i];
  cnt[i]++;
}

void del(int i) {
  cnt[i]--;
  sum -= cnt[i];
}

long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n >> m;
  maxn = sqrt(n);
  for (int i = 1; i <= n; i++) cin >> c[i];
  for (int i = 0; i < m; i++) cin >> a[i].l >> a[i].r, a[i].id = i;
  sort(a, a + m);
  for (int i = 0, l = 1, r = 0; i < m; i++) {  // Concrete implementation
    if (a[i].l == a[i].r) {
      ans1[a[i].id] = 0, ans2[a[i].id] = 1;
      continue;
    }
    while (l > a[i].l) add(c[--l]);
    while (r < a[i].r) add(c[++r]);
    while (l < a[i].l) del(c[l++]);
    while (r > a[i].r) del(c[r--]);
    ans1[a[i].id] = sum;
    ans2[a[i].id] = (long long)(r - l + 1) * (r - l) / 2;
  }
  for (int i = 0; i < m; i++) {
    if (ans1[i] != 0) {
      long long g = gcd(ans1[i], ans2[i]);
      ans1[i] /= g, ans2[i] /= g;
    } else
      ans2[i] = 1;
    cout << ans1[i] << '/' << ans2[i] << '\n';
  }
  return 0;
}

Optimizing ordinary Mo's algorithm

Process

Consider the following data:

// Suppose the block size is 2
1 1
2 100
3 1
4 100

Manual simulation shows that the r pointer moves about 300 times. After processing the first block, $l = 2, r = 100$; at this point, moving the l pointer twice would give the fourth query's answer. However, we move the r pointer to 1 to obtain the third query's answer, then move it to 100 to obtain the fourth query's answer, adding more than 90 pointer moves. How can this be optimized? We use odd-even sorting.

What is odd-even sorting? For queries in odd-numbered blocks, sort r in ascending order; for queries in even-numbered blocks, sort r in descending order. After processing an odd block, the r pointer handles the even block while returning, then moves toward n to process the next odd block, reducing its movement. In general, this optimization makes the program about 30% faster.

Implementation

Sorting code:

Compressed form

// clang-format off
// A detail will be discussed shortly
int unit; // Block size
struct node {
  int l, r, id;
  bool operator < (const node &x) const {
    return l / unit == x.l / unit ? (r == x.r ? 0 : ((l / unit) & 1) ^ (r < x.r)) : l < x.l;
  }
};

Uncompressed form

struct node {
  int l, r, id;

  bool operator<(const node &x) const {
    if (l / unit != x.l / unit) return l < x.l;
    // Do not write less-than-or-equal (greater-than-or-equal) on the next two lines, or an error will occur (see the detail below)
    if ((l / unit) & 1) return r < x.r;
    return r > x.r;
  }
};

In the compressed form, without the special case r == x.r, the problem above occurs when l is in the same odd block and r is equal (verify it manually). In the uncompressed form, writing less-than-or-equal (greater-than-or-equal) causes the same problem.

References

• Mo's algorithm notes | Sengxian's Blog