xii. Mo's Algorithm

Offline range queries where the window $[L,R)$ can be extended and shrunk by one element in $O(1)$ (or $O(\log )$): count distinct, pairs of equal values, sum of $f({\text{cnt}}_v)$, mex with a value-sqrt, mode with a count-of-counts. Reorder the queries so that the total pointer movement is $O(n\sqrt{q})$.

Classic Mo

template<class Add, class Rem, class Ans>
void mo(int n, const vector<pair<int, int>>& qs, Add add, Rem rem, Ans ans) {   // queries [l, r)
    int q = sz(qs), B = max(1, int(n / sqrt(max(q, 1))));
    vector<int> ord(q); iota(all(ord), 0);
    sort(all(ord), [&](int i, int j) {
        int bi = qs[i].first / B, bj = qs[j].first / B;
        if (bi != bj) return bi < bj;
        return bi & 1 ? qs[i].second > qs[j].second : qs[i].second < qs[j].second;
    });
    int L = 0, R = 0;
    for (int id : ord) {
        auto [l, r] = qs[id];
        while (L > l) add(--L);                 // grow first, then shrink:
        while (R < r) add(R++);                 // the window is never "negative"
        while (L < l) rem(L++);
        while (R > r) rem(--R);
        ans(id);
    }
}

The alternating direction of $r$ (“odd-even sort”) saves about a third of the $r$ movement. Hilbert order (sort queries by the index of $(l,r)$ on a Hilbert curve of side $2^k\ge n$) is another 20-40% in practice:

ll hilbert(int x, int y, int k = 20) {   // 2^k >= n
    ll d = 0;
    for (int s = 1 << (k - 1); s; s >>= 1) {
        int rx = (x & s) > 0, ry = (y & s) > 0;
        d += ll(s) * s * ((3 * rx) ^ ry);
        if (!ry) { if (rx) x = s - 1 - x, y = s - 1 - y; swap(x, y); }
    }
    return d;
}

Proof: $O(n\sqrt{q})$ pointer moves with $B=n/\sqrt{q}$

Queries are grouped by the block of $l$, so there are at most $n/B$ groups. Within a group, $r$ is monotone, so $R$ moves at most $n$ per group, plus at most $n$ when switching groups: $O(n\cdot n/B)$ in total. Each query moves $L$ by at most $2B$ within its group (both endpoints lie in the same block), and switching groups moves $L$ forward by at most $2B$ more, so $L$ moves $O(qB+n)$ in total. The sum $n^2/B+qB$ is minimised at $B=n/\sqrt{q}$, giving $O(n\sqrt{q})$. Correctness does not depend on the order: every answer is read when the window equals exactly $[l,r)$, and add/rem maintain the window’s state as an invariant. Doing all extensions before shrinks ensures that $L\le R$ throughout, so rem is only called on elements that are in the window.

When the add/remove cost is not $O(1)$: if add is $O(\log n)$ (Fenwick for “count of values $<x$”), the total is $O(n\sqrt{q}\log n)$. Usually better: keep $O(1)$ updates and $O(\sqrt{V})$ queries via a value-sqrt structure (counts per value + counts per value block). Then the total is $O(n\sqrt{q}+q\sqrt{V})$. Classic targets: Codeforces 940F “Machine Learning” (mex of frequency counts, with updates), and “count of distinct values in a range” under point updates.

Mo with updates

Queries become $(l,r,t)$ where $t$ = number of updates before the query. Sort by $(\lfloor l/B\rfloor ,\lfloor r/B\rfloor ,t)$ with $B\approx n^{2/3}$. Moving $t$ applies/undoes one update: if the position is inside the window, remove the old value and add the new one; always write the array.

struct Upd { int pos, before, after; };            // fill "before" by simulating the array while reading
auto apply = [&](int k, bool fwd) {
    int p = ups[k].pos, v = fwd ? ups[k].after : ups[k].before;
    if (L <= p && p < R) { rem(p); a[p] = v; add(p); } else a[p] = v;
};
// per query: while (T < q.t) apply(T++, 1); while (T > q.t) apply(--T, 0); then move L and R as usual

Proof: $O(n^{5/3})$ total moves when $n\approx q\approx u$

Group queries by the pair of blocks $(\lfloor l/B\rfloor ,\lfloor r/B\rfloor )$: there are $O((n/B{)}^2)$ groups. Within a group, $t$ is monotone, so $T$ moves $O(u)$ per group: $O(u{n}^2/B^2)$ in total. $L$ and $R$ move $O(B)$ per query inside a group and $O(n)$ per group change in the worst case (but $R$ only sweeps once per $l$-block, so $O(n\cdot n/B)$). Total: $O(qB+n^2/B+u{n}^2/B^2)$. With $B=n^{2/3}$ and $n\approx q\approx u$ every term is $O(n^{5/3})$. Using $B=\sqrt{n}$ instead makes the time term $O(nu)$, quadratic.

Mo on trees (path queries)

Euler tour where each vertex appears twice: at entry ($\text{tin}$) and exit ($\text{tout}$), array length $2n$. For a path $u\to v$ with ${\text{tin}}_u\le {\text{tin}}_v$ and $w=\text{lca}(u,v)$:

• if $w=u$, the range is $[{\text{tin}}_u,{\text{tin}}_v]$;
• otherwise the range is $[{\text{tout}}_u,{\text{tin}}_v]$ and $w$ must be added separately (toggle it before reading the answer and toggle it back).

Both add and rem become toggle(vertex): a vertex whose two occurrences both lie in the range cancels out.

Proof: the vertices appearing exactly once in the range are exactly the path (minus possibly the LCA)

Case $w=u$: the range runs from entering $u$ to entering $v$. A vertex $x$ appears once iff we entered it and haven’t left it by the time we enter $v$, which means $x$ is an ancestor of $v$ that is entered after (or at) $u$, i.e. a vertex on the path from $u$ down to $v$. Every other vertex in the range was fully explored (entered and exited) inside it. Case $w\ne u$: the range starts at the exit of $u$. Vertices on the path from $u$ up to (but excluding) $w$ are exited inside the range and were entered before it: they appear once. Vertices on the path from $w$ down to $v$ (excluding $w$) are entered inside the range and not yet exited: once. $w$ itself was entered before and is exited after: zero times, hence the separate toggle. Any other vertex is either entirely inside (twice) or entirely outside (zero).

Subtree queries need no trick: a subtree is the contiguous range $[{\text{tin}}_v,{\text{tout}}_v)$ of the usual single-occurrence Euler tour, and plain array Mo’s applies with no toggling. They’re usually better done by small-to-large (DSU on Tree) or a Fenwick tree over that same Euler-tour range; reach for Mo’s only when the aggregate resists both.

Situation	Method	Cost
Aggregate is associative, no updates	binary lifting	$O(\log n)$
Aggregate is associative, with updates	HLD + segment tree	$O({\log }^{2}n)$
Aggregate needs add/remove semantics	Mo’s on trees	$O(n\sqrt{n})$
Counting over all paths	centroid decomposition	$O(n\log n)$
Small vertex subsets per query	virtual tree	$O(k\log n)$

Mo’s on trees is the fallback for aggregates like “number of distinct values” that HLD cannot merge — its niche is real but narrow. The Hilbert-curve speedup for the query order applies here too, same as array Mo’s.

Rollback Mo (add-only)

When removing is impossible but you can add and undo (max, mode with only increasing counts, DSU connectivity, linear basis, “max distance between equal values”): group by the block of $l$, sort by $r$. For each block, reset to empty with $R$ at the block end. For each query, grow $R$ (persistently within the block), snapshot, add $[l,\text{blockEnd})$ on the left, answer, roll back. Queries entirely inside one block are brute-forced from empty.

template<class AL, class AR, class Snap, class Roll, class Reset, class Ans>
void moRollback(int n, const vector<pair<int, int>>& qs, AL addL, AR addR, Snap snap, Roll roll, Reset reset, Ans ans) {
    int q = sz(qs); if (!q) return;
    int B = max(1, int(n / sqrt(q)));
    vector<int> ord(q); iota(all(ord), 0);
    sort(all(ord), [&](int i, int j) { return pair(qs[i].first / B, qs[i].second) < pair(qs[j].first / B, qs[j].second); });
    for (int i = 0; i < q;) {
        int blk = qs[ord[i]].first / B, end = min(n, (blk + 1) * B), r = end;
        reset();
        for (; i < q && qs[ord[i]].first / B == blk; i++) {
            auto [l, rr] = qs[ord[i]];
            if (rr <= end) { snap(); for (int j = l; j < rr; j++) addR(j); }
            else { while (r < rr) addR(r++); snap(); for (int j = end - 1; j >= l; j--) addL(j); }
            ans(ord[i]); roll();
        }
    }
}

Implement rollback with a history stack of (cell, old value) pairs pushed in add; snap records the stack size and the scalar answer. For range connectivity (components using edges $l..r-1$, CodeChef GERALD07), add merges in a DSU with union by size and no path compression, and rollback pops merges: $O((m\sqrt{q}+q)\log n)$.

Proof: rollback Mo does $O(n\sqrt{q})$ adds and the answers are correct

Within one $l$-block, $r$ only increases, so the right part grows by at most $n$ per block: $O(n\cdot n/B)$. Each query adds at most $B$ elements on the left (from $l$ to the block end) and undoes them, and brute-forced queries cost at most $B$ each: $O(qB)$. With $B=n/\sqrt{q}$ the total is $O(n\sqrt{q})$. Correctness: before the left additions, the state is exactly $[\text{end},r)$, built purely by additions; after adding $[l,\text{end})$ it is exactly $[l,r)$; rollback restores $[\text{end},r)$ because the undo log contains every changed cell.

Second offline Mo (Mo with prefix queries)

For answers of the form ${\sum }_{l\le i<j<r}f(a_i,a_j)$ (range inversions, pairs with $\text{popcount}(a_i\oplus a_j)=k$) where moving a pointer by one is too expensive ($O(\log n)$ each makes $O(n\sqrt{n}\log n)$). Moving $R$ from $r$ to $r+1$ changes the answer by $F(a_r,[l,r))=F(a_r,[0,r))-F(a_r,[0,l))$:

• the first term is a prefix quantity, precomputed for every $r$ in one sweep;
• the second term is “elements $a_r..a_{r^{\prime }}$ against the prefix $[0,l)$”, recorded as one task per pointer run (not per step) at prefix $l$.

A final sweep inserts $a_0,a_1,\dots$ into a structure with $O(\sqrt{V})$ insert and $O(1)$ query, and answers each task by iterating its range. Total: $O(n\sqrt{q})$ queries + $O(n\sqrt{V})$ inserts, $O(n)$ memory. The answers come out as differences, so take prefix sums along the processing order. Luogu P5047 (range inversions), P4887.

Proof: the decomposition is exact and the cost is $O(n\sqrt{q}+n\sqrt{V})$

Since $f$ is summed over pairs, the change from adding $a_r$ on the right of $[l,r)$ is ${\sum }_{i\in [l,r)}f(a_i,a_r)$, which equals the sum over $[0,r)$ minus the sum over $[0,l)$; the left side is symmetric with $f(a_l,\cdot )$ over the window. Shrinking subtracts the same quantities. The number of task elements equals the total pointer movement of classic Mo, $O(n\sqrt{q})$, and each costs one $O(1)$ query; there are $n$ inserts of $O(\sqrt{V})$ each. The structure holds only one prefix at a time, so memory is $O(n+q)$ (the tasks are $O(q)$ ranges, not $O(n\sqrt{q})$ items).

Other variants

Variant	Idea	Cost
two ranges $[l_1,r_1)\cup [l_2,r_2)$ (e.g. two Euler-tour subtrees, CF 1767F)	four pointers, sort by blocks of $l_1,r_1,l_2$ then $r_2$, block $n/q^{1/4}$	$O(n{q}^{3/4})$
online Mo (forced online, with point updates)	store the structure for every pair of blocks; query = stored $(i,j)$ + $O(B)$ loose elements; update touches $O((n/B{)}^2)$ structures	$B=n^{2/3}$: $O(n^{2/3})$ adds per query, $O(n^{2/3})$ structures per update, $O(n^{2/3})$ copies in memory
bitset Mo	window state is a bitset of values; answer = bitset operations (e.g. “can $a\cdot b=x$ / $a-b=x$“)	$O(n\sqrt{q}+qV/64)$
Mo on 2D (submatrices)	pointers per side	$O(nm\cdot q^{3/4})$-ish, rarely good

Checklist

• Block size $n/\sqrt{q}$, not $\sqrt{n}$, when $q\ll n$.
• Extend before shrinking; with half-open windows, start from $L=R=0$.
• Compress values; keep counts in plain arrays, not maps.
• If the answer needs “max of counts”, maintain count-of-counts (removal never needs a search because the max drops by at most one), or use rollback Mo.
• Prefer an $O(n\log n)$ offline sweep when the query is decomposable (distinct values in a range: sweep $r$, keep only the last occurrence in a Fenwick).