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).
- ✓
addandremoveof 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
- 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.
- Why √n blocks? R travels n per block (n/B blocks) and L travels B per query; B = √n balances n²/B and qB.
- What does "offline" mean? All queries are known before answering, so they can be reordered.
- What must add and remove do? Update the current answer in O(1) when one element enters or leaves the window.
- Why store answers by index? Queries are processed in sorted order but must be printed in input order.
- When can't you use Mo? Online queries, or (without the extended version) updates between queries.
- 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
addandremove(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