Why this matters when you build with AI
AI tools answer range-query questions with a loop over each query. That costs about n * q steps, which is fine for a sample and far too slow at the limits of a contest problem. When you ask for something faster, the tool often produces a window-moving solution with no sorting step, or a sorted solution that never resets its state between blocks. Both look right on the sample.
Mo's algorithm has three places where a small mistake gives a wrong number and no error: the order of the pointer loops, the block size, and the undo step in the rollback variant. The check is the same one used in the prefix sum lesson. Write a brute force that answers each query the slow obvious way, generate many small random inputs with empty and full-length windows, and compare the two outputs. Then time the code at a worst-case size and count the pointer moves, because the move count is the same on every machine.
A prompt to test an AI tool
Give the tool this prompt, then check its answer against the list below.
Write a C++17 solution for this problem. The array has n values up to 200000, each below 100000. There are q queries up to 200000, and each query is a half-open window [l, r). For each query print how many values occur exactly once in the window. Use Mo's algorithm with blocks on l and alternating r. Also write a brute force, and a random test that compares the two on 2000 small inputs that include empty windows. Print the code, the block size you chose and the test result, and nothing else.A good answer has these parts. The sort uses the block of l and alternates the direction of r. Adding a value and removing a value each update a counter of values whose count is exactly one, and the removal reverses the addition. The random test includes l = r and both ends of the array. The answer says which block size it used and why. Check that the counter changes only when a count crosses one, and that the brute force is not the same code as the fast solver.
Scope and how the code was checked
Every program in this lesson was compiled with g++ -O2 -std=c++17 on the machine that wrote it. That machine runs Linux under WSL2 and uses g++ 15.2.0. Each solver was compared with a brute force on random small inputs before any timing was done. The timings come from one machine, and two runs of the same benchmark differed by up to 1.6 times. Read the move counts as the stable numbers and the times as rough. On your machine the times will differ.
No outside source is cited. The bounds below are proved in the text. Everything else is what the programs printed.
The idea: one window that moves
A window is a range of positions. This lesson uses half-open windows, as the prefix sum lesson does. The window [l, r) holds the positions l to r - 1, so [1, 4) holds three values.
Take a = [1, 2, 1, 3, 2, 1]. Suppose the first query is [0, 3), which holds [1, 2, 1], and the second query is [1, 5), which holds [2, 1, 3, 2]. To move from the first window to the second, remove a[0] (the value 1), then add a[3] (the value 3) and a[4] (the value 2). That is three moves. Answering each query from scratch would add 3 values for the first and 4 for the second. With many queries, the moves add up. The trick is to order the queries so the total number of moves stays small.
The problem used in this lesson is: for a window, compute the sum of cnt[v] squared over all values v, where cnt[v] is how many times v appears in the window. Call it the sum of squares. It is a frequency-based query, and it can be updated one element at a time:
- Adding value
xchangescnt[x]fromctoc + 1. The sum grows by(c + 1)^2 - c^2 = 2c + 1. - Removing value
xchangescnt[x]fromctoc - 1. The sum shrinks byc^2 - (c - 1)^2 = 2c - 1.
Both updates take constant time. An update that can be exactly undone is called invertible. The sum of squares is invertible, because removing a value is the exact reverse of adding it. A maximum is not invertible. If you remove the largest value, you cannot know the new maximum without more information. The rollback section handles that case.
The standard technique
Split the positions into blocks of size B. Block number l / B holds every query whose window starts at l. Sort the queries by the block of l. Inside each block, sort by r: ascending in odd-numbered blocks and descending in even-numbered blocks. This alternating order is the one the solver below uses by default.
The reason for this order is a bound on the work. Inside one block, l stays within a range of B positions, so the left pointer moves at most B steps for each query. Over all queries that is at most q * B left moves. Inside one block, r moves in one direction only, so it moves at most n steps per block. There are n / B blocks, so the right pointer moves at most n * n / B times in total.
Adding the two bounds gives q * B + n * n / B. With B = sqrt(n), that is O((n + q) * sqrt(n)). The big-O notation here means "grows no faster than this, up to a constant factor". With B = n / sqrt(q), both terms equal n * sqrt(q), which is the same order when q is close to n. The benchmark below tries several block sizes around n / sqrt(q).
The alternating direction matters. Without it, the right pointer has to jump back to the smallest r of the next block after every block, which can mean a move across almost the whole array. The big-O bound stays the same, but the constant is about twice as large. The benchmark below shows the cost.
Here is the C++ version. It contains the sort, the four pointer loops, the Hilbert index (explained in its own section), a brute force, a random test and a timing run. The pointer loops run in this order: extend R, extend L, shrink R, shrink L. Extending first keeps the window from ever having a negative length, which is the habit to keep. A reversed order also gave correct answers in the test, for a reason explained in the mistakes section.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Query { int l, r; }; // half-open window [l, r)
// Hilbert index of cell (x, y) on a side x side grid (side is a power of two).
ll hilbert_index(ll side, ll x, ll y) {
ll d = 0;
for (ll s = side / 2; s > 0; s /= 2) {
ll rx = (x & s) > 0;
ll ry = (y & s) > 0;
d += s * s * ((3 * rx) ^ ry);
if (ry == 0) {
if (rx == 1) { x = side - 1 - x; y = side - 1 - y; }
swap(x, y);
}
}
return d;
}
// order 0: blocks of l, r alternating up and down.
// order 1: Hilbert order on (l, r).
// order 2: blocks of l, r always ascending.
struct MoStats { vector<ll> ans; ll moves; };
MoStats mo_sumsq(const vector<int> &a, const vector<Query> &qs, int V, int B, int order) {
int n = a.size(), q = qs.size();
vector<int> ord(q);
iota(ord.begin(), ord.end(), 0);
if (order == 1) {
ll side = 1;
while (side < n + 1) side <<= 1;
vector<ll> key(q);
for (int i = 0; i < q; i++) key[i] = hilbert_index(side, qs[i].l, qs[i].r);
sort(ord.begin(), ord.end(), [&](int i, int j) { return key[i] < key[j]; });
} else {
sort(ord.begin(), ord.end(), [&](int i, int j) {
int bi = qs[i].l / B, bj = qs[j].l / B;
if (bi != bj) return bi < bj;
if (order == 0 && (bi & 1)) return qs[i].r > qs[j].r;
return qs[i].r < qs[j].r;
});
}
vector<ll> cnt(V, 0), ans(q, 0);
ll cur = 0, moves = 0;
int L = 0, R = 0; // current window [L, R)
for (int id : ord) {
int l = qs[id].l, r = qs[id].r;
while (R < r) { int x = a[R++]; cur += 2 * cnt[x] + 1; cnt[x]++; moves++; }
while (L > l) { int x = a[--L]; cur += 2 * cnt[x] + 1; cnt[x]++; moves++; }
while (R > r) { int x = a[--R]; cnt[x]--; cur -= 2 * cnt[x] + 1; moves++; }
while (L < l) { int x = a[L++]; cnt[x]--; cur -= 2 * cnt[x] + 1; moves++; }
ans[id] = cur;
}
return {ans, moves};
}
vector<ll> brute_sumsq(const vector<int> &a, const vector<Query> &qs, int V) {
vector<ll> out;
for (const auto &[l, r] : qs) {
vector<ll> c(V, 0);
for (int i = l; i < r; i++) c[a[i]]++;
ll s = 0;
for (int v = 0; v < V; v++) s += c[v] * c[v];
out.push_back(s);
}
return out;
}
void test_hilbert() {
for (ll side : {2, 4, 8, 16}) {
vector<pair<ll, ll>> at(side * side, {-1, -1});
for (ll x = 0; x < side; x++)
for (ll y = 0; y < side; y++) {
ll d = hilbert_index(side, x, y);
assert(d >= 0 && d < side * side);
assert(at[d].first == -1); // no two cells share an index
at[d] = {x, y};
}
for (ll d = 1; d < side * side; d++) { // consecutive indices are neighbours
ll dist = llabs(at[d].first - at[d - 1].first) + llabs(at[d].second - at[d - 1].second);
assert(dist == 1);
}
printf("hilbert side=%lld: bijection and neighbour check ok\n", side);
}
}
void random_tests() {
mt19937 rng(12345);
const int ITER = 3000;
for (int it = 0; it < ITER; it++) {
int n = rng() % 30 + 1, V = rng() % 6 + 1, q = rng() % 30 + 1;
vector<int> a(n);
for (auto &x : a) x = rng() % V;
vector<Query> qs(q);
for (auto &[l, r] : qs) {
l = rng() % (n + 1);
r = l + rng() % (n - l + 1); // empty windows allowed
}
auto expect = brute_sumsq(a, qs, V);
for (int order = 0; order < 3; order++)
for (int B : {1, 2, 3, n}) {
auto got = mo_sumsq(a, qs, V, B, order).ans;
if (got != expect) {
printf("MISMATCH it=%d order=%d B=%d\n", it, order, B);
return;
}
}
}
printf("random tests: %d inputs x 3 orders x 4 block sizes, all match brute force\n", ITER);
}
void worked_example() {
vector<int> a = {1, 2, 1, 3, 2, 1};
vector<Query> qs = {{0, 3}, {1, 5}, {2, 6}, {4, 6}};
auto got = mo_sumsq(a, qs, 4, 2, 0).ans;
auto expect = brute_sumsq(a, qs, 4);
for (size_t i = 0; i < qs.size(); i++)
printf("query [%d,%d) sumsq=%lld brute=%lld\n", qs[i].l, qs[i].r, got[i], expect[i]);
}
void bench() {
const int n = 200000, q = 200000, V = 100000;
mt19937 rng(7);
vector<int> a(n);
for (auto &x : a) x = rng() % V;
vector<Query> qs(q);
for (auto &[l, r] : qs) {
l = rng() % n;
r = l + 1 + rng() % (n - l);
}
double b0 = n / sqrt((double)q);
printf("n=%d q=%d V=%d, default block size n/sqrt(q)=%.1f\n", n, q, V, b0);
printf("%-22s %8s %14s %10s %12s\n", "variant", "B", "moves", "ms", "checksum");
for (double f : {0.25, 0.5, 1.0, 2.0, 4.0}) {
int B = max(1, (int)(b0 * f));
auto t0 = chrono::steady_clock::now();
auto st = mo_sumsq(a, qs, V, B, 0);
auto t1 = chrono::steady_clock::now();
ll sum = 0;
for (ll x : st.ans) sum ^= x;
printf("%-22s %8d %14lld %10.1f %12lld\n", ("alternating x" + to_string(f).substr(0, 4)).c_str(), B,
st.moves, chrono::duration<double, milli>(t1 - t0).count(), sum);
}
for (int order : {2, 1}) {
int B = max(1, (int)b0);
auto t0 = chrono::steady_clock::now();
auto st = mo_sumsq(a, qs, V, B, order);
auto t1 = chrono::steady_clock::now();
ll sum = 0;
for (ll x : st.ans) sum ^= x;
printf("%-22s %8d %14lld %10.1f %12lld\n", order == 2 ? "block, r ascending" : "hilbert", B,
st.moves, chrono::duration<double, milli>(t1 - t0).count(), sum);
}
}
int main(int argc, char **argv) {
if (argc > 1 && string(argv[1]) == "bench") {
bench();
return 0;
}
test_hilbert();
random_tests();
worked_example();
return 0;
}Compile and run it with these commands. The first run checks the Hilbert index, runs 3000 random tests and prints the worked example. The second run is the timing run.
g++ -O2 -std=c++17 -Wall -Wextra -o mos_sumsq mos_sumsq.cpp
./mos_sumsq
./mos_sumsq benchOutput of the first run on the machine that wrote this lesson:
hilbert side=2: bijection and neighbour check ok
hilbert side=4: bijection and neighbour check ok
hilbert side=8: bijection and neighbour check ok
hilbert side=16: bijection and neighbour check ok
random tests: 3000 inputs x 3 orders x 4 block sizes, all match brute force
query [0,3) sumsq=5 brute=5
query [1,5) sumsq=6 brute=6
query [2,6) sumsq=6 brute=6
query [4,6) sumsq=2 brute=2Check the first query by hand. The window [1, 2, 1] has two 1s and one 2, so the sum is 2^2 + 1^2 = 5. The second query [2, 1, 3, 2] has one 1, one 3 and two 2s, so 1 + 1 + 4 = 6. Both match.
Hilbert order
Block order is not the only way to sort. A Hilbert curve is a path that visits every cell of a square grid once, and cells that are consecutive on the path are neighbours on the grid. Map each query to the point (l, r) on a grid, compute the position of that point along the Hilbert path, and sort the queries by that position. Queries that are close in (l, r) tend to end up close in the sorted list, so the window moves a short distance between neighbouring queries.
The function hilbert_index computes the position along the path with a loop over the bits of the coordinates. The check test_hilbert confirms two properties on grids of side 2, 4, 8 and 16: every cell gets a different index, and cells with consecutive indices are next to each other. Passing that check does not prove the order is faster. It proves the index is a valid path. Speed is a separate question, and only measurement answers it.
Block size and ordering: what the benchmark printed
The benchmark uses 200000 positions, 200000 queries with random windows, and values below 100000. The default block size is n / sqrt(q), which is 447 here. First run on the machine that wrote this lesson:
n=200000 q=200000 V=100000, default block size n/sqrt(q)=447.2
variant B moves ms checksum
alternating x0.25 111 186065640 1313.6 687211
alternating x0.50 223 104279985 591.3 687211
alternating x1.00 447 74456912 438.2 687211
alternating x2.00 894 81706899 470.8 687211
alternating x4.00 1788 129056878 579.3 687211
block, r ascending 447 118606707 835.8 687211
hilbert 447 73881107 275.4 687211The second run printed:
alternating x0.25 111 186065640 1819.0 687211
alternating x0.50 223 104279985 1016.7 687211
alternating x1.00 447 74456912 630.6 687211
alternating x2.00 894 81706899 410.0 687211
alternating x4.00 1788 129056878 561.2 687211
block, r ascending 447 118606707 934.6 687211
hilbert 447 73881107 438.7 687211What is stable across both runs:
- The move counts never change, because they depend only on the input and the sort. They are the numbers to compare.
- The checksum matches on every row, so every variant produced the same answers.
- A block size of about one-quarter of the default costs the most moves for the alternating order, because the left pointer moves more often between blocks. A block size of four times the default also costs more moves, because the right pointer moves more within each long block. The minimum is near the default in this run.
- Sorting by block with
ralways ascending costs 118.6 million moves, against 74.5 million for alternating. The extra right-pointer jumps are the cost. - Hilbert order had about the same number of moves as alternating (73.9 million against 74.5 million). It was faster in both runs, but the gap was 1.6 times in one run and 1.4 times in the other, which is about the size of the noise. The program does not show why it was faster. Test it on your own queries before you pick it.
The rollback variant
Some structures cannot remove a value. The mode frequency of a window is the largest count of any single value in it. Adding a value can only raise a count, so the maximum is easy to keep. Removing a value would need a record of every count, which is more work than the window itself.
Rollback Mo's keeps the window growing to the right and never shrinks it. It works like this:
- Split positions into blocks of size
Band sort the queries by the block ofl, then byr. - Keep a shared window
[blockEnd, R)that starts empty at the right edge of the block. It only grows. - For a query whose
ris past the block, grow the shared window tor. Save the current maximum. Add the values in[l, blockEnd)one at a time, record the maximum as the answer, then undo those additions by lowering their counts and restore the saved maximum. - A query that ends inside its own block has fewer than
Bvalues. Count it directly with a second array.
The cost matches the sum-of-squares solver. Each query adds at most B values, which is q * B in total. The shared window grows at most n per block, which is n * n / B. The undo step costs the same as the adds, so the bound does not change.
Here is the C++ version with a brute force and a random test:
#include <bits/stdc++.h>
using namespace std;
struct Query { int l, r; }; // half-open window [l, r)
// Mo's with rollback. Only additions are allowed. The answer is the largest
// number of times any value occurs in the window (the mode frequency).
// Adding a value can only raise a count, so the maximum is easy to keep.
// Removing a value would need a multiset of counts, so the window is never shrunk.
vector<int> mo_rollback_maxfreq(const vector<int> &a, const vector<Query> &qs, int V) {
int n = a.size(), q = qs.size();
int B = max(1, (int)(n / sqrt((double)max(1, q))));
vector<int> ord(q);
iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [&](int i, int j) {
int bi = qs[i].l / B, bj = qs[j].l / B;
if (bi != bj) return bi < bj;
return qs[i].r < qs[j].r;
});
vector<int> cnt(V, 0), small(V, 0), ans(q, 0);
int curBlock = -1, blockEnd = 0, R = 0, best = 0;
for (int id : ord) {
int l = qs[id].l, r = qs[id].r;
int b = l / B;
if (b != curBlock) { // new block: empty the shared window, start at its right edge
for (int i = blockEnd; i < R; i++) cnt[a[i]]--;
curBlock = b;
blockEnd = min(n, (b + 1) * B);
R = blockEnd;
best = 0;
}
if (r <= blockEnd) { // whole query inside one block: at most B values, count directly
int bestSmall = 0;
for (int i = l; i < r; i++) bestSmall = max(bestSmall, ++small[a[i]]);
for (int i = l; i < r; i++) small[a[i]]--;
ans[id] = bestSmall;
continue;
}
while (R < r) { // shared window grows to the right only
best = max(best, ++cnt[a[R]]);
R++;
}
int saved = best; // the part [l, blockEnd) is added, then undone
for (int i = blockEnd - 1; i >= l; i--) best = max(best, ++cnt[a[i]]);
ans[id] = best;
for (int i = l; i < blockEnd; i++) cnt[a[i]]--;
best = saved;
}
for (int i = blockEnd; i < R; i++) cnt[a[i]]--;
return ans;
}
vector<int> brute_maxfreq(const vector<int> &a, const vector<Query> &qs, int V) {
vector<int> out;
for (const auto &[l, r] : qs) {
vector<int> c(V, 0);
int best = 0;
for (int i = l; i < r; i++) best = max(best, ++c[a[i]]);
out.push_back(best);
}
return out;
}
void random_tests() {
mt19937 rng(2024);
const int ITER = 3000;
for (int it = 0; it < ITER; it++) {
int n = rng() % 40 + 1, V = rng() % 7 + 1, q = rng() % 40 + 1;
vector<int> a(n);
for (auto &x : a) x = rng() % V;
vector<Query> qs(q);
for (auto &[l, r] : qs) {
l = rng() % n;
r = l + 1 + rng() % (n - l); // non-empty windows
}
if (mo_rollback_maxfreq(a, qs, V) != brute_maxfreq(a, qs, V)) {
printf("MISMATCH at iteration %d\n", it);
return;
}
}
printf("random tests: %d inputs, all match brute force\n", ITER);
}
int main() {
vector<int> a = {1, 2, 1, 3, 2, 1, 1};
vector<Query> qs = {{0, 3}, {1, 5}, {2, 7}, {4, 7}, {3, 4}};
auto got = mo_rollback_maxfreq(a, qs, 4);
auto expect = brute_maxfreq(a, qs, 4);
for (size_t i = 0; i < qs.size(); i++)
printf("query [%d,%d) maxfreq=%d brute=%d\n", qs[i].l, qs[i].r, got[i], expect[i]);
random_tests();
return 0;
}Output on the machine that wrote this lesson:
query [0,3) maxfreq=2 brute=2
query [1,5) maxfreq=2 brute=2
query [2,7) maxfreq=3 brute=3
query [4,7) maxfreq=2 brute=2
query [3,4) maxfreq=1 brute=1
random tests: 3000 inputs, all match brute forceCheck the third query by hand. The window [2, 7) holds [1, 3, 2, 1, 1], and the value 1 occurs three times, so the answer is 3.
The rollback code does not have a timing run in this lesson. The bound is the same as the sum-of-squares solver, and the exercise asks you to time it yourself.
Hands-on exercise
Work on your own machine with any g++ or clang++ that accepts -std=c++17. Create a folder, save the sum-of-squares program as mos_sumsq.cpp, and run the three commands from the section above.
- Confirm that the first run prints all four Hilbert lines and the line
random tests: 3000 inputs x 3 orders x 4 block sizes, all match brute force. If it printsMISMATCH, stop and read the first mismatch line. - Change
mt19937 rng(12345)to a different seed inrandom_tests, rebuild and run again. The line must still say all match. - Run the benchmark twice. Write down the move counts for each row. The counts must be identical in both runs. Write down the times too, and note how far apart the two runs are.
- Add a new order,
order == 3, that sorts bylonly, with no block split and no alternation. Predict whether it will have more moves than the alternating order on this benchmark, then measure. Write one sentence on why.
Show the answer
Step 1 and step 2 should match the text exactly except for the seed. Step 3: the move counts match the values printed above on the same kind of machine, and the times differ. Step 4: sorting by l alone leaves r in random order inside each l group, so the right pointer can jump across the whole array between neighbouring queries. Expect more moves than the alternating order, and the measurement should show it. If it does not, check that the new order really changed the sort.
Common mistakes
Overflow in the sum of squares
The code above keeps the sum in a long long. With 200000 equal values in one window, cnt is 200000 and its square is 40000000000. If the sum is stored in a 32-bit int, the result overflows, because a 32-bit int holds values only up to 2147483647. The symptom is a negative or nonsense answer on a window that holds many copies of one value. The sample tests usually do not catch it, because their windows are short.
Forgetting to restore the saved maximum
In the rollback code, the line best = saved; puts back the maximum that was valid before the temporary additions. Remove that line and the next query inherits a maximum from the previous query's temporary additions. Here is the real output of the same program with that line deleted:
query [0,3) maxfreq=2 brute=2
query [1,5) maxfreq=2 brute=2
query [2,7) maxfreq=3 brute=3
query [4,7) maxfreq=2 brute=2
query [3,4) maxfreq=1 brute=1
MISMATCH at iteration 0The five sample queries still match, because the inflated maximum only shows when a later window has a smaller answer than an earlier one. The random test finds it on its first iteration. Always run the random test after any change to the undo step.
Reversing the pointer loops
The standard order is: extend R, extend L, shrink R, shrink L. A common AI-written variant shrinks first. For the sum of squares, that variant still gives correct answers. The update rule is exact even when a count briefly goes negative, so the final counts and the sum are right. The order does matter for structures that reject a removal of a value that is not present, such as a set-based answer or a check that asserts the count is never negative. Keep the safe order by default, and use the random test to verify any change.
Sorting by l only
Without blocks, the queries are sorted by l alone. The right pointer then moves back and forth across the array. In the benchmark, sorting by block with r always ascending needed 118.6 million moves against 74.5 million for alternating order, and it was slower in both runs.
Mixing half-open and closed ranges
The code uses [l, r) everywhere. If one helper treats r as included, the window is one value too long and the answer is off by a small amount. Write the convention in the function's comment and check the empty range [3, 3), which must return 0.
Checklist
- Write the brute force first and generate random inputs with empty windows and windows at the edges.
- Keep one half-open convention and write it next to every function that takes a range.
- Use
long longfor any sum of squares or sum of counts. - Extend the window before shrinking it, and keep that order unless you have a reason to change it.
- For a non-invertible answer, use rollback. Restore every piece of state the temporary additions changed.
- Count pointer moves on a worst-case input. Use the count, not one timing, to compare orders and block sizes.
- Run the random test again after every change to the sort key, the block size or the undo step.
Summary
Mo's algorithm answers range queries by moving one window through the array. Sorting the queries by block of the left end, with the right end alternating in direction, keeps the total moves near n * sqrt(q). The Hilbert order can save moves on some inputs, and the benchmark showed that as a measurement, not a rule. Rollback handles answers that cannot undo a removal by only adding and then taking the temporary additions back out.
Practice
Each problem has a short hint in its statement. Attempt the problem on paper or in code before opening the answer. Every answer is a short argument, not a full program, unless the problem asks for code.
Problem 1: values seen at least k times
Using the sum-of-squares solver as a base, change the answer to the number of values that occur at least k times in the window, for a fixed k given at the start. Write the two update lines for add and remove. Hint: keep one counter that changes only when some cnt[x] crosses k.
Show the answer
Keep a counter good, the number of values whose count is at least k. On add, write if (++cnt[x] == k) good++;. The count reaches k exactly once, when it goes from k - 1 to k. On remove, write if (cnt[x]-- == k) good--;. The post-decrement compares the old count, so good drops exactly when the count falls from k to k - 1. With k = 1 the counter is the number of distinct values. Test it with the random test pattern and k set to 1, 2 and 3.
Problem 2: why B = sqrt(n) gives the stated bound
Prove that with block size B = sqrt(n), the total number of pointer moves is O((n + q) * sqrt(n)).
Show the answer
Left pointer: inside a block, l stays in a range of B values, so each query moves it at most B steps, which is q * sqrt(n) in total. Right pointer: inside a block, r moves in one direction only, so at most n steps per block. There are n / B = sqrt(n) blocks, so the right pointer moves at most n * sqrt(n) in total. The sum is q * sqrt(n) + n * sqrt(n) = (n + q) * sqrt(n). Without alternation, the right pointer can also jump back up to n at each block boundary. That doubles the constant but leaves the big-O bound unchanged.
Problem 3: a min query with rollback
Adapt the rollback solver to answer the minimum value in a window instead of the mode frequency. Say which lines change and why the rollback step still works.
Show the answer
Replace the counts with a plain array lookup and the max with min over the values themselves. Adding a value can only lower the minimum, so the answer is still easy to keep during the adds. The temporary additions can only lower the minimum, so the undo step is just restoring the saved value. The window must still grow right only, so the same block structure and bound apply.