SyntaxPilot
Courses/Competitive Programming/Lesson 66
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

Competitive Programming · Lesson 66 of 90

Mo's algorithm

queued

These are the notes for Competitive Programming episode 66. When all range queries are known in advance (offline), keep one window a[L..R] with add(i) and remove(i) that update the answer in O(1), and move the window's ends from query to query. The cost is the total distance the ends travel. In input order that can be about n per query (TLE), but sorting the queries by (block of l, then r) with blocks of B ≈ √n, Mo's order, makes the total O((n + q)·√n). Street Food Walk (distinct values in a range) shows a set per query (TLE), a window in input order (still TLE), Mo's order, and the bug of printing answers in the sorted order (3 4 2 4 1 instead of 3 4 2 1 4). Sock Pairs (equal pairs in a range) only needs a new add and remove; subtracting before decrementing gives 7 −2 −1 −8. Stress tests pass. Every C++ example was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13, the same command as the SyntaxPilot compiler); all outputs below are real.

The real-life hook

A postman who delivers letters in the order they arrived at the post office rides across the city and back again and again. A smart postman sorts the letters first, by area and then by house number inside the area. Within an area he rides the main road only forwards and makes short side trips; then he moves on to the next area. The total ride is tiny. Mo's algorithm sorts range queries the same way before "riding" the window over them.

Problem M1 · Street Food Walk

(Written for this course, in the style of a classic "distinct values in a range" problem.)

  • Input: n q (n, q ≤ 2 · 10^5), dishes a[1..n] (≤ 10^6), then q walks l r.
  • Output per walk: the number of different dishes among stalls l..r.
  • All walks are read before anything is printed, so they may be answered in any order (offline).
8 5
5 2 5 7 2 2 9 5
1 4
3 8
2 3
6 6
1 8

Answers: 3, 4, 2, 1, 4.

The obvious attempt: a set per walk (TLE)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n, q, a[200001], cnt[1000001], ql[200001], qr[200001];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 0; i < q; i++) cin >> ql[i] >> qr[i];
    for (int i = 0; i < q; i++) {
        set<int> dishes(a + ql[i], a + qr[i] + 1);   // every stall of the walk
        cout << dishes.size() << "\n";
    }
}
3
4
2
1
4

With 2 · 10^5 random walks:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n, q, a[200001], cnt[1000001], ql[200001], qr[200001];

int main() {
    n = q = 200000;                          // 2·10^5 stalls and walks
    mt19937 rng(66);
    for (int i = 1; i <= n; i++) a[i] = rng() % 1000000 + 1;
    for (int i = 0; i < q; i++) {
        ql[i] = rng() % n + 1, qr[i] = rng() % n + 1;
        if (ql[i] > qr[i]) swap(ql[i], qr[i]);
    }
    ll check = 0;
    for (int i = 0; i < q; i++) {
        set<int> dishes(a + ql[i], a + qr[i] + 1);
        check += dishes.size();
    }
    cout << check << "\n";
}
Time Limit Exceeded

A sliding window

Neighbouring walks share most of their stalls, so keep one window a[L..R] and cnt[dish] for the dishes inside it:

  • add(i): if (cnt[a[i]]++ == 0) distinct++; (a new dish)
  • remove(i): if (--cnt[a[i]] == 0) distinct--; (the last one left)
  • moveTo(l, r): grow first (R < r, L > l), then shrink (R > r, L < l), one step at a time.

Each step is O(1), so the cost is how far L and R travel in total.

Window in input order: still TLE

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n, q, a[200001], cnt[1000001], ql[200001], qr[200001];
int L = 1, R = 0, distinct = 0;                 // the window a[L..R]
void add(int i) { if (cnt[a[i]]++ == 0) distinct++; }      // a new dish
void remove(int i) { if (--cnt[a[i]] == 0) distinct--; }   // last one gone
void moveTo(int l, int r) {
    while (R < r) add(++R);
    while (L > l) add(--L);
    while (R > r) remove(R--);
    while (L < l) remove(L++);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 0; i < q; i++) cin >> ql[i] >> qr[i];
    for (int i = 0; i < q; i++) {                // in the order they came
        moveTo(ql[i], qr[i]);
        cout << distinct << "\n";
    }
}
3
4
2
1
4
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n, q, a[200001], cnt[1000001], ql[200001], qr[200001];
int L = 1, R = 0, distinct = 0;                 // the window a[L..R]
void add(int i) { if (cnt[a[i]]++ == 0) distinct++; }      // a new dish
void remove(int i) { if (--cnt[a[i]] == 0) distinct--; }   // last one gone
void moveTo(int l, int r) {
    while (R < r) add(++R);
    while (L > l) add(--L);
    while (R > r) remove(R--);
    while (L < l) remove(L++);
}

int main() {
    n = q = 200000;                          // 2·10^5 stalls and walks
    mt19937 rng(66);
    for (int i = 1; i <= n; i++) a[i] = rng() % 1000000 + 1;
    for (int i = 0; i < q; i++) {
        ql[i] = rng() % n + 1, qr[i] = rng() % n + 1;
        if (ql[i] > qr[i]) swap(ql[i], qr[i]);
    }
    ll check = 0;
    for (int i = 0; i < q; i++) {
        moveTo(ql[i], qr[i]);
        check += distinct;
    }
    cout << check << "\n";
}
Time Limit Exceeded

Random walks jump all over the street: the ends travel about n per walk, n · q in total.

Mo's order

Sort the walks by l / B (B ≈ √n), and inside the same block by r.

  • Inside one block of l, r is sorted, so R only moves right: at most n steps per block, n / B blocks → n² / B = n√n.
  • L stays inside its block (or moves to the next): at most about B per walk → q√n (plus n for the block changes).
  • Total: O((n + q)·√n), about 2 · 10^8 O(1) steps for n = q = 2 · 10^5. The sort adds O(q log q).

On the sample (B = 2): walks 1 (1–4) and 5 (1–8) in block 0, then 3 (2–3) and 2 (3–8) in block 1, then 4 (6–6). The answers are produced in the order 1, 5, 3, 2, 4, so each one must be stored at its walk's own index.

The bug: printing in the sorted order

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n, q, a[200001], cnt[1000001], ql[200001], qr[200001];
int L = 1, R = 0, distinct = 0;                 // the window a[L..R]
void add(int i) { if (cnt[a[i]]++ == 0) distinct++; }      // a new dish
void remove(int i) { if (--cnt[a[i]] == 0) distinct--; }   // last one gone
void moveTo(int l, int r) {
    while (R < r) add(++R);
    while (L > l) add(--L);
    while (R > r) remove(R--);
    while (L < l) remove(L++);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 0; i < q; i++) cin >> ql[i] >> qr[i];
    int B = max(1, (int)sqrt(n));
    vector<int> ord(q);
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](int x, int y) {      // Mo's order
        if (ql[x] / B != ql[y] / B) return ql[x] / B < ql[y] / B;
        return qr[x] < qr[y];
    });
    for (int i : ord) {
        moveTo(ql[i], qr[i]);
        cout << distinct << "\n";              // printed right away
    }
}
3
4
2
4
1

Expected 3 4 2 1 4: the right numbers in the wrong order.

The fix: ans[i]

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n, q, a[200001], cnt[1000001], ql[200001], qr[200001];
int L = 1, R = 0, distinct = 0;                 // the window a[L..R]
void add(int i) { if (cnt[a[i]]++ == 0) distinct++; }      // a new dish
void remove(int i) { if (--cnt[a[i]] == 0) distinct--; }   // last one gone
void moveTo(int l, int r) {
    while (R < r) add(++R);
    while (L > l) add(--L);
    while (R > r) remove(R--);
    while (L < l) remove(L++);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 0; i < q; i++) cin >> ql[i] >> qr[i];
    int B = max(1, (int)sqrt(n));
    vector<int> ord(q);
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](int x, int y) {      // Mo's order
        if (ql[x] / B != ql[y] / B) return ql[x] / B < ql[y] / B;
        return qr[x] < qr[y];
    });
    vector<int> ans(q);
    for (int i : ord) {
        moveTo(ql[i], qr[i]);
        ans[i] = distinct;                           // back in its own place
    }
    for (int i = 0; i < q; i++) cout << ans[i] << "\n";
}
3
4
2
1
4
1 1
42
1 1
1

The big test (sum of all answers as a check number), in well under a second:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n, q, a[200001], cnt[1000001], ql[200001], qr[200001];
int L = 1, R = 0, distinct = 0;                 // the window a[L..R]
void add(int i) { if (cnt[a[i]]++ == 0) distinct++; }      // a new dish
void remove(int i) { if (--cnt[a[i]] == 0) distinct--; }   // last one gone
void moveTo(int l, int r) {
    while (R < r) add(++R);
    while (L > l) add(--L);
    while (R > r) remove(R--);
    while (L < l) remove(L++);
}

int main() {
    n = q = 200000;                          // 2·10^5 stalls and walks
    mt19937 rng(66);
    for (int i = 1; i <= n; i++) a[i] = rng() % 1000000 + 1;
    for (int i = 0; i < q; i++) {
        ql[i] = rng() % n + 1, qr[i] = rng() % n + 1;
        if (ql[i] > qr[i]) swap(ql[i], qr[i]);
    }
    int B = max(1, (int)sqrt(n));
    vector<int> ord(q);
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](int x, int y) {      // Mo's order
        if (ql[x] / B != ql[y] / B) return ql[x] / B < ql[y] / B;
        return qr[x] < qr[y];
    });
    ll check = 0;
    for (int i : ord) {
        moveTo(ql[i], qr[i]);
        check += distinct;
    }
    cout << check << "\n";
}
12634618332

Stress test

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n, q, a[200001], cnt[1000001], ql[200001], qr[200001];
int L = 1, R = 0, distinct = 0;                 // the window a[L..R]
void add(int i) { if (cnt[a[i]]++ == 0) distinct++; }      // a new dish
void remove(int i) { if (--cnt[a[i]] == 0) distinct--; }   // last one gone
void moveTo(int l, int r) {
    while (R < r) add(++R);
    while (L > l) add(--L);
    while (R > r) remove(R--);
    while (L < l) remove(L++);
}

int main() {
    mt19937 rng(66);
    for (int t = 1; t <= 500; t++) {
        while (L <= R) remove(L++);                   // empty the window first
        L = 1, R = 0;
        n = rng() % 40 + 1, q = rng() % 40 + 1;
        for (int i = 1; i <= n; i++) a[i] = rng() % 8 + 1;
        for (int i = 0; i < q; i++) {
            ql[i] = rng() % n + 1, qr[i] = rng() % n + 1;
            if (ql[i] > qr[i]) swap(ql[i], qr[i]);
        }
        int B = max(1, (int)sqrt(n));
        vector<int> ord(q);
        iota(ord.begin(), ord.end(), 0);
        sort(ord.begin(), ord.end(), [&](int x, int y) {      // Mo's order
            if (ql[x] / B != ql[y] / B) return ql[x] / B < ql[y] / B;
            return qr[x] < qr[y];
        });
        vector<int> ans(q);
        for (int i : ord) moveTo(ql[i], qr[i]), ans[i] = distinct;
        for (int i = 0; i < q; i++)
            if (ans[i] != (int)set<int>(a + ql[i], a + qr[i] + 1).size()) {
                cout << "mismatch on test " << t;
                return 0;
            }
    }
    cout << "all 500 tests passed";
}
all 500 tests passed

Problem M2 · Sock Pairs

(Written for this course.)

  • Input: n q (n, q ≤ 2 · 10^5), colours a[1..n] (≤ n), then q queries l r.
  • Output per query: the number of pairs i < j in [l, r] with a[i] = a[j] (long long: up to about 2 · 10^10).
7 4
1 2 1 1 3 2 1
1 7
2 5
3 7
5 5

Answers: 7 (colour 1 appears 4 times: 6 pairs, plus one pair of colour 2), 1, 3, 0.

Window. Adding a sock of colour x pairs it with the cnt[x] socks of colour x already inside: pairs += cnt[x]++. Removing it breaks the pairs with the others that stay: pairs -= --cnt[x] (decrease first). Mo's order is unchanged.

The bug: subtract before decrement

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n, q, a[200001], cnt[200001], ql[200001], qr[200001];
int L = 1, R = 0;
ll pairs = 0;                                   // equal pairs inside a[L..R]
void add(int i) { pairs += cnt[a[i]]++; }      // pairs with the same colour already in
void remove(int i) { pairs -= cnt[a[i]]--;  }
void moveTo(int l, int r) {
    while (R < r) add(++R);
    while (L > l) add(--L);
    while (R > r) remove(R--);
    while (L < l) remove(L++);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 0; i < q; i++) cin >> ql[i] >> qr[i];
    int B = max(1, (int)sqrt(n));
    vector<int> ord(q);
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](int x, int y) {      // Mo's order
        if (ql[x] / B != ql[y] / B) return ql[x] / B < ql[y] / B;
        return qr[x] < qr[y];
    });
    vector<ll> ans(q);
    for (int i : ord) {
        moveTo(ql[i], qr[i]);
        ans[i] = pairs;
    }
    for (int i = 0; i < q; i++) cout << ans[i] << "\n";
}
7
-2
-1
-8

A negative number of pairs: the removed sock was counted as pairing with itself.

The fix

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n, q, a[200001], cnt[200001], ql[200001], qr[200001];
int L = 1, R = 0;
ll pairs = 0;                                   // equal pairs inside a[L..R]
void add(int i) { pairs += cnt[a[i]]++; }      // pairs with the same colour already in
void remove(int i) { pairs -= --cnt[a[i]]; }
void moveTo(int l, int r) {
    while (R < r) add(++R);
    while (L > l) add(--L);
    while (R > r) remove(R--);
    while (L < l) remove(L++);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 0; i < q; i++) cin >> ql[i] >> qr[i];
    int B = max(1, (int)sqrt(n));
    vector<int> ord(q);
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](int x, int y) {      // Mo's order
        if (ql[x] / B != ql[y] / B) return ql[x] / B < ql[y] / B;
        return qr[x] < qr[y];
    });
    vector<ll> ans(q);
    for (int i : ord) {
        moveTo(ql[i], qr[i]);
        ans[i] = pairs;
    }
    for (int i = 0; i < q; i++) cout << ans[i] << "\n";
}
7
1
3
0
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n, q, a[200001], cnt[200001], ql[200001], qr[200001];
int L = 1, R = 0;
ll pairs = 0;                                   // equal pairs inside a[L..R]
void add(int i) { pairs += cnt[a[i]]++; }      // pairs with the same colour already in
void remove(int i) { pairs -= --cnt[a[i]]; }
void moveTo(int l, int r) {
    while (R < r) add(++R);
    while (L > l) add(--L);
    while (R > r) remove(R--);
    while (L < l) remove(L++);
}

int main() {
    n = q = 200000;
    mt19937 rng(66);
    for (int i = 1; i <= n; i++) a[i] = rng() % 1000 + 1;
    for (int i = 0; i < q; i++) {
        ql[i] = rng() % n + 1, qr[i] = rng() % n + 1;
        if (ql[i] > qr[i]) swap(ql[i], qr[i]);
    }
    int B = max(1, (int)sqrt(n));
    vector<int> ord(q);
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](int x, int y) {      // Mo's order
        if (ql[x] / B != ql[y] / B) return ql[x] / B < ql[y] / B;
        return qr[x] < qr[y];
    });
    ll check = 0;
    for (int i : ord) {
        moveTo(ql[i], qr[i]);
        check ^= pairs;
    }
    cout << check << "\n";
}
4805768

Stress test

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n, q, a[200001], cnt[200001], ql[200001], qr[200001];
int L = 1, R = 0;
ll pairs = 0;                                   // equal pairs inside a[L..R]
void add(int i) { pairs += cnt[a[i]]++; }      // pairs with the same colour already in
void remove(int i) { pairs -= --cnt[a[i]]; }
void moveTo(int l, int r) {
    while (R < r) add(++R);
    while (L > l) add(--L);
    while (R > r) remove(R--);
    while (L < l) remove(L++);
}

int main() {
    mt19937 rng(66);
    for (int t = 1; t <= 500; t++) {
        while (L <= R) remove(L++);
        L = 1, R = 0;
        n = rng() % 40 + 1, q = rng() % 40 + 1;
        for (int i = 1; i <= n; i++) a[i] = rng() % 5 + 1;
        for (int i = 0; i < q; i++) {
            ql[i] = rng() % n + 1, qr[i] = rng() % n + 1;
            if (ql[i] > qr[i]) swap(ql[i], qr[i]);
        }
        int B = max(1, (int)sqrt(n));
        vector<int> ord(q);
        iota(ord.begin(), ord.end(), 0);
        sort(ord.begin(), ord.end(), [&](int x, int y) {      // Mo's order
            if (ql[x] / B != ql[y] / B) return ql[x] / B < ql[y] / B;
            return qr[x] < qr[y];
        });
        vector<ll> ans(q);
        for (int i : ord) moveTo(ql[i], qr[i]), ans[i] = pairs;
        for (int i = 0; i < q; i++) {
            ll slow = 0;
            for (int x = ql[i]; x <= qr[i]; x++)
                for (int y = x + 1; y <= qr[i]; y++) slow += a[x] == a[y];
            if (ans[i] != slow) { cout << "mismatch on test " << t; return 0; }
        }
    }
    cout << "all 500 tests passed";
}
all 500 tests passed

Complexity vs the constraints

Method Cost Verdict
set per walk O(q · n log n) TLE
window, input order O(q · n) moves TLE
window, Mo's order O((n + q)·√n) moves + O(q log q) sort accepted

Memory is O(n + q + max value): the counts, the queries and the answers.

When Mo's algorithm fits

  • ✓ All queries known in advance (offline).
  • ✓ add and remove of one element are O(1) (or cheap): counts, distinct values, pairs, frequency tricks.
  • ✗ Updates between queries: needs Mo's algorithm with updates (time as a third coordinate, blocks of about n^(2/3)).
  • ✗ Online queries (a query depends on the previous answer): they can't be reordered.
  • Speed-up: odd-even ordering: in odd-numbered blocks sort r descending, in even ones ascending, so R doesn't jump back to the left at every new block (used in practice problem 3).

Common mistakes (and the real outputs)

Mistake What you see Why Fix
a set per query Time Limit Exceeded rebuilt every time a window
window in input order Time Limit Exceeded ends jump ~n per query Mo's order
printing in the sorted order 3 4 2 4 1 (expected 3 4 2 1 4) answers out of place ans[i], print at the end
pairs -= cnt[x]-- 7 −2 −1 −8 (expected 7 1 3 0) the sock pairs with itself pairs -= --cnt[x]
shrinking before growing wrong counts / negative indices the window becomes empty-negative for a moment grow first, then shrink
int for the pair count overflow up to 2 · 10^10 long long
l / B with B = 0 for tiny n division by zero sqrt(0) B = max(1, …)

Mini project

Write a generic Mo's template: a function that takes the queries plus add, remove and get lambdas, sorts with the odd-even trick and returns the answers in input order. Use it for distinct values, equal pairs, and "values appearing at least twice"; stress-test each against a brute force.

Practice

These are the homework problems from the episode. The C++ solution was checked against a brute force on 300 random tests.

1. Count the values that appear at least twice in l..r.

Solution

add: when a count becomes 2, twice++; remove: when a count drops from 2, twice--. This version also uses the odd-even ordering.

#include <bits/stdc++.h>
using namespace std;

int n, q, a[200001], cnt[1000001], ql[200001], qr[200001];
int L = 1, R = 0, twice = 0;                       // values that appear at least twice
void add(int i) { if (++cnt[a[i]] == 2) twice++; }
void remove(int i) { if (cnt[a[i]]-- == 2) twice--; }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 0; i < q; i++) cin >> ql[i] >> qr[i];
    int B = max(1, (int)sqrt(n));
    vector<int> ord(q), ans(q);
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](int x, int y) {
        if (ql[x] / B != ql[y] / B) return ql[x] / B < ql[y] / B;
        return (ql[x] / B % 2) ? qr[x] > qr[y] : qr[x] < qr[y];   // odd-even trick
    });
    for (int i : ord) {
        while (R < qr[i]) add(++R);
        while (L > ql[i]) add(--L);
        while (R > qr[i]) remove(R--);
        while (L < ql[i]) remove(L++);
        ans[i] = twice;
    }
    for (int i = 0; i < q; i++) cout << ans[i] << "\n";
}

On the street-food sample:

1
2
0
0
2

2. The highest frequency of any value in l..r.

Solution

Keep cnt[x] and also freqOf[c] = how many values have count c. add: freqOf[cnt[x]]--, cnt[x]++, freqOf[cnt[x]]++, and best = max(best, cnt[x]). remove: if freqOf[cnt[x]] becomes 0 and cnt[x] == best, then best--; then decrease. Both stay O(1) because the best frequency can only drop by one per removal.

3. The odd-even trick.

Answer

Replace the comparator's second line with return (ql[x] / B % 2) ? qr[x] > qr[y] : qr[x] < qr[y]; (see the solution to problem 1). R then sweeps right in one block and left in the next instead of returning to the start, which often makes Mo's algorithm about 1.5–2 times faster.

4. The sum of cnt² over the window.

Solution

When cnt[x] goes from c to c + 1, the sum grows by (c + 1)² − c² = 2c + 1; when it goes from c to c − 1, it shrinks by 2c − 1. Both are O(1), so Mo's algorithm applies directly. (The answer is n + 2 · pairs, so it's the sock problem in disguise.)

Quick quiz

B = 3. In which order does Mo answer w1 = (4, 9), w2 = (1, 7), w3 = (2, 3), w4 = (5, 6)?

A) w3, w2, w4, w1 · B) w2, w3, w4, w1 · C) w1, w2, w3, w4 · D) w3, w4, w2, w1

Answer

A. l / 3: w1 → 1, w2 → 0, w3 → 0, w4 → 1. Block 0 by r: w3 (3), w2 (7). Block 1 by r: w4 (6), w1 (9).

Interview questions

  1. What is Mo's algorithm? An offline technique that sorts range queries by (block of l, r) and moves a window with O(1) add/remove between them, for O((n + q)·√n) total.
  2. Why √n blocks? R travels n per block (n/B blocks) and L travels B per query; B = √n balances n²/B and qB.
  3. What does "offline" mean? All queries are known before answering, so they can be reordered.
  4. What must add and remove do? Update the current answer in O(1) when one element enters or leaves the window.
  5. Why store answers by index? Queries are processed in sorted order but must be printed in input order.
  6. When can't you use Mo? Online queries, or (without the extended version) updates between queries.
  7. What is the odd-even trick? Alternating the direction of r between blocks to avoid R jumping back.

Glossary

Term Meaning Example
Offline queries All queries are read before any is answered the walks
Online queries Each query must be answered before the next is read not for Mo
Window The current range a[L..R] the stalls the walk covers
add(i) / remove(i) Update the answer when a[i] enters / leaves the window cnt[a[i]]++
Distinct count How many different values are in a range dishes
Mo's order Sort by (l / B, r) with B ≈ √n walks 1, 5, 3, 2, 4
Block of l l / B, the group a query belongs to ql[x] / B
Total travel How far L and R move over all queries the cost of Mo
iota Fills 0, 1, 2, … into a range iota(ord.begin(), ord.end(), 0)
Comparator A function telling sort which comes first the lambda in sort
ans[i] Storing each answer at its query's index printing in input order
Equal pairs Pairs i < j with a[i] = a[j] sock pairs
Odd-even trick Alternate r's direction between blocks practice 3
Stress test Comparing a fast solution with a slow, surely-correct one on many random inputs all 500 tests passed
Time Limit Exceeded (TLE) Too slow input order
Wrong Answer (WA) A wrong output 3 4 2 4 1
Persistent segment tree A segment tree that keeps every version next episode

Summary

  • Offline range queries + O(1) add/remove → Mo's algorithm.
  • Sort by (l / B, r), B ≈ √n: total O((n + q)·√n) moves.
  • Grow first, then shrink; store ans[i] and print in input order.
  • A new problem only needs a new add and remove (decrease before subtracting for pairs).
  • Odd-even ordering is a free speed-up.

Solutions in C++, Java and Python

Problem M1 · Street Food Walk

C++

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n, q, a[200001], cnt[1000001], ql[200001], qr[200001];
int L = 1, R = 0, distinct = 0;                 // the window a[L..R]
void add(int i) { if (cnt[a[i]]++ == 0) distinct++; }      // a new dish
void remove(int i) { if (--cnt[a[i]] == 0) distinct--; }   // last one gone
void moveTo(int l, int r) {
    while (R < r) add(++R);
    while (L > l) add(--L);
    while (R > r) remove(R--);
    while (L < l) remove(L++);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 0; i < q; i++) cin >> ql[i] >> qr[i];
    int B = max(1, (int)sqrt(n));
    vector<int> ord(q);
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](int x, int y) {      // Mo's order
        if (ql[x] / B != ql[y] / B) return ql[x] / B < ql[y] / B;
        return qr[x] < qr[y];
    });
    vector<int> ans(q);
    for (int i : ord) {
        moveTo(ql[i], qr[i]);
        ans[i] = distinct;                           // back in its own place
    }
    for (int i = 0; i < q; i++) cout << ans[i] << "\n";
}
3
4
2
1
4

Java

import java.util.*;
import java.io.*;

public class Main {
    static int[] a, cnt;
    static int distinct = 0;
    static void add(int i) { if (cnt[a[i]]++ == 0) distinct++; }
    static void remove(int i) { if (--cnt[a[i]] == 0) distinct--; }
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedInputStream(System.in));
        in.nextToken(); int n = (int) in.nval; in.nextToken(); int q = (int) in.nval;
        a = new int[n + 1]; cnt = new int[1000001];
        for (int i = 1; i <= n; i++) { in.nextToken(); a[i] = (int) in.nval; }
        int[] ql = new int[q], qr = new int[q];
        for (int i = 0; i < q; i++) { in.nextToken(); ql[i] = (int) in.nval; in.nextToken(); qr[i] = (int) in.nval; }
        int B = Math.max(1, (int) Math.sqrt(n));
        Integer[] ord = new Integer[q];
        for (int i = 0; i < q; i++) ord[i] = i;
        Arrays.sort(ord, (x, y) -> ql[x] / B != ql[y] / B ? Integer.compare(ql[x] / B, ql[y] / B) : Integer.compare(qr[x], qr[y]));
        int[] ans = new int[q];
        int L = 1, R = 0;
        for (int i : ord) {
            while (R < qr[i]) add(++R);
            while (L > ql[i]) add(--L);
            while (R > qr[i]) remove(R--);
            while (L < ql[i]) remove(L++);
            ans[i] = distinct;                          // back in its own place
        }
        StringBuilder sb = new StringBuilder();
        for (int x : ans) sb.append(x).append('\n');
        System.out.print(sb);
    }
}
3
4
2
1
4

Python

import sys
from math import isqrt

def main():
    data = sys.stdin.buffer.read().split()
    n, q = int(data[0]), int(data[1])
    a = [0] + [int(x) for x in data[2:n + 2]]
    ql = [int(x) for x in data[n + 2::2]]
    qr = [int(x) for x in data[n + 3::2]]
    B = max(1, isqrt(n))
    ord_ = sorted(range(q), key=lambda i: (ql[i] // B, qr[i]))    # Mo's order
    cnt = [0] * (max(a) + 1)
    ans = [0] * q
    L, R, distinct = 1, 0, 0
    for i in ord_:
        l, r = ql[i], qr[i]
        while R < r:
            R += 1; cnt[a[R]] += 1
            if cnt[a[R]] == 1: distinct += 1
        while L > l:
            L -= 1; cnt[a[L]] += 1
            if cnt[a[L]] == 1: distinct += 1
        while R > r:
            cnt[a[R]] -= 1
            if cnt[a[R]] == 0: distinct -= 1
            R -= 1
        while L < l:
            cnt[a[L]] -= 1
            if cnt[a[L]] == 0: distinct -= 1
            L += 1
        ans[i] = distinct
    print("\n".join(map(str, ans)))

main()
3
4
2
1
4

(Python is too slow for the full limits here; it is for understanding.)

Problem M2 · Sock Pairs

C++

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n, q, a[200001], cnt[200001], ql[200001], qr[200001];
int L = 1, R = 0;
ll pairs = 0;                                   // equal pairs inside a[L..R]
void add(int i) { pairs += cnt[a[i]]++; }      // pairs with the same colour already in
void remove(int i) { pairs -= --cnt[a[i]]; }
void moveTo(int l, int r) {
    while (R < r) add(++R);
    while (L > l) add(--L);
    while (R > r) remove(R--);
    while (L < l) remove(L++);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 0; i < q; i++) cin >> ql[i] >> qr[i];
    int B = max(1, (int)sqrt(n));
    vector<int> ord(q);
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](int x, int y) {      // Mo's order
        if (ql[x] / B != ql[y] / B) return ql[x] / B < ql[y] / B;
        return qr[x] < qr[y];
    });
    vector<ll> ans(q);
    for (int i : ord) {
        moveTo(ql[i], qr[i]);
        ans[i] = pairs;
    }
    for (int i = 0; i < q; i++) cout << ans[i] << "\n";
}
7
1
3
0

Java

import java.util.*;
import java.io.*;

public class Main {
    static int[] a, cnt;
    static long pairs = 0;
    static void add(int i) { pairs += cnt[a[i]]++; }       // pairs with the same colour already in
    static void remove(int i) { pairs -= --cnt[a[i]]; }    // decrease first, then subtract
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedInputStream(System.in));
        in.nextToken(); int n = (int) in.nval; in.nextToken(); int q = (int) in.nval;
        a = new int[n + 1]; cnt = new int[n + 1];
        for (int i = 1; i <= n; i++) { in.nextToken(); a[i] = (int) in.nval; }
        int[] ql = new int[q], qr = new int[q];
        for (int i = 0; i < q; i++) { in.nextToken(); ql[i] = (int) in.nval; in.nextToken(); qr[i] = (int) in.nval; }
        int B = Math.max(1, (int) Math.sqrt(n));
        Integer[] ord = new Integer[q];
        for (int i = 0; i < q; i++) ord[i] = i;
        Arrays.sort(ord, (x, y) -> ql[x] / B != ql[y] / B ? Integer.compare(ql[x] / B, ql[y] / B) : Integer.compare(qr[x], qr[y]));
        long[] ans = new long[q];
        int L = 1, R = 0;
        for (int i : ord) {
            while (R < qr[i]) add(++R);
            while (L > ql[i]) add(--L);
            while (R > qr[i]) remove(R--);
            while (L < ql[i]) remove(L++);
            ans[i] = pairs;
        }
        StringBuilder sb = new StringBuilder();
        for (long x : ans) sb.append(x).append('\n');
        System.out.print(sb);
    }
}
7
1
3
0

Python

import sys
from math import isqrt

def main():
    data = sys.stdin.buffer.read().split()
    n, q = int(data[0]), int(data[1])
    a = [0] + [int(x) for x in data[2:n + 2]]
    ql = [int(x) for x in data[n + 2::2]]
    qr = [int(x) for x in data[n + 3::2]]
    B = max(1, isqrt(n))
    ord_ = sorted(range(q), key=lambda i: (ql[i] // B, qr[i]))
    cnt = [0] * (max(a) + 1)
    ans = [0] * q
    L, R, pairs = 1, 0, 0
    for i in ord_:
        l, r = ql[i], qr[i]
        while R < r:
            R += 1; pairs += cnt[a[R]]; cnt[a[R]] += 1    # pairs with the socks already in
        while L > l:
            L -= 1; pairs += cnt[a[L]]; cnt[a[L]] += 1
        while R > r:
            cnt[a[R]] -= 1; pairs -= cnt[a[R]]; R -= 1    # decrease first, then subtract
        while L < l:
            cnt[a[L]] -= 1; pairs -= cnt[a[L]]; L += 1
        ans[i] = pairs
    print("\n".join(map(str, ans)))

main()
7
1
3
0