Hello everyone!

In contests, problems involving range queries appear quite often. Most problems provide queries offline, which allows for greater flexibility in solving them, but often they reduce to using a segment tree or Mo's algorithm. However, sometimes a problem that is easily solvable offline with Mo's algorithm becomes interesting in the online version. In such cases, some people try to maintain something like $$$500$$$ different states of Mo's algorithm — I never really understood what was meant by that.

Today, I managed to come up with an online version of Mo's algorithm that works in $$$O(n^{\frac{5}{3}})$$$ time and memory for usual problems (where moving the pointers is done in $$$O(1)$$$). For asymptotic analysis, I'll assume $$$n = q$$$. I'm not the first to come up with this idea. As it turns out, here и here was a discussion where this idea was proposed, but I also want to do this as I've never heard of it before.

In this blog, I want to break down how to solve a problem from a recent Educational Round using online Mo's algorithm.

2043G - Problem with Queries

This problem has too much going on — update queries and even encoded inputs. Let's first try solving the offline version without update queries. I should clarify that instead of counting the number of indices $$$i \lt j$$$ where $$$a_i \neq a_j$$$, I'll count the opposite — the number of pairs where $$$a_i = a_j$$$. From this value, it's easy to derive the answer to the original problem, but counting pairs with equal values is slightly simpler to maintain.

The problem itself is a simple exercise on Mo's algorithm.

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

#define all(x) x.begin(), x.end()

const int N = 1e5 + 10;
const int B = 320; // roughly sqrt N
int a[N];
int cnt[N];
ll sum = 0;

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

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

int L = 0, R = -1; // the pointers

void move(int l, int r) { // move pointers to the query point
    while (R < r) {
        ++R;
        add(a[R]);
    }
    while (R > r) {
        del(a[R]);
        R--;
    }
    while (L > l) {
        L--;
        add(a[L]);
    }
    while (L < l) {
        del(a[L]);
        L++;
    }
}

struct query {
    int l, r, i;
};

signed main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        a[i]--;
    }
    int queries;
    cin >> queries;
    vector<query> q(queries);
    vector<ll> ans(queries);
    for (int i = 0; i < queries; i++) {
        int l, r;
        cin >> l >> r;
        l--;
        r--;
        q[i] = {l, r, i};
    }
    sort(all(q), [&](const query &a, const query &b) {
        int al = a.l / B;
        int bl = b.l / B;
        if (al != bl)
            return al < bl;
        return a.r < b.r;
    });
    for (auto &[l, r, i] : q) {
        move(l, r);
        ans[i] = sum;
    }
    for (int i = 0; i < queries; i++)
        cout << ans[i] << ' ';
    cout << '\n';
    return 0;
}

I want to look at the asymptotic analysis from a geometric perspective. Let the block size for Mo's algorithm be $$$B \approx \sqrt{n}$$$. Briefly, we divide the plane into squares of size $$$B \times B$$$ and traverse them in the correct order.

Now, let's add the constraint of online queries. Unfortunately, in this version, we can't choose the order of traversing the squares, and we might need to enter some square multiple times, so a different approach is needed. Clearly, maintaining just one pair of pointers won't suffice, as answering each query would then take $$$O(n)$$$ time, which is too slow. Let's define a state as all the necessary information we usually maintain for one segment. In this problem that would be frequency array $$$cnt$$$, number of pairs of indices $$$sum$$$ and pointers $$$L$$$ and $$$R$$$. I want to create multiple states so that we can quickly move from one of them to our query.

Let $$$B \approx n^{\frac{2}{3}}$$$. Now, we have few squares — only $$$\frac{n^2}{B^2} = n^{\frac{2}{3}}$$$. I want to create a state in every square, so that I can reach every query quickly. Indeed, within a square the distance between points doesn't exceed $$$2B$$$, which already gives us acceptable query processing time. The algorithm can be described as follows:

1. Determine the square containing the query.
2. If no queries have been made in this square before, initialize it in $$$O(n)$$$ time. Create a state at the query point.
3. Otherwise, we have a state within a distance of at most $$$2B$$$, so we can answer the query in $$$O(B)$$$ time.

Since there are few squares, all initializations will run in $$$O(n^{\frac{5}{3}})$$$ total time, and the total pointer movements will not exceed $$$O(qB) = O(nB) = O(n^{\frac{5}{3}})$$$.

Great, we’ve learned how to perform online Mo's algorithm faster than $$$O(nq)$$$. But can we also support update queries? And if so, do we need to sacrifice anything? The answers to these questions are yes and no! Typically, with update queries, 3D Mo's is used, which introduces time as a third dimension, turning the traversal into a three-dimensional space. To move the third parameter $$$T$$$, we check if the modified position lies within the current state and perform del and add if necessary. But nothing stops us from doing the same for all blocks. Since there are $$$O(n^{\frac{2}{3}})$$$ of them, the runtime remains the same.

With this idea, it’s clear how to solve the problem. And it’s quite easy to implement.

My solution: 329249141

It's truly phenomenal, imho, that such a simple idea as Mo's algorithm can work online, even with updates!

P.S.: Actually, as it turns out, this is more of an interpretation of the problem analysis rather than a different solution. The division into squares — the same as dividing into blocks. Initializing a state in each square is equivalent to precomputing answers for each pair of blocks, and moving the pointers — corresponds to adding elements from the edges of incomplete blocks.