Алгоритм Мо (Mo's algorithm): как сортировка по блокам даёт O((n+q) sqrt n)?

Алгоритм Мо — оффлайн-техника: обрабатываем все запросы в специальном порядке, поддерживая текущее окно [curL, curR] и его ответ, двигая границы по одному и инкрементально пересчитывая ответ функциями add/remove.

Порядок: сортируем запросы по номеру блока левой границы l / B (B = sqrt(n)), а внутри блока — по r. Тогда:

• r внутри одного блока l монотонно растёт → суммарно по блоку r проходит O(n); блоков sqrt(n) → суммарно по r: O(n sqrt n).
• l гуляет внутри блока на O(B) = O(sqrt n) за запрос → суммарно O(q sqrt n). Итого O((n + q) sqrt n).

int B;
struct Query { int l, r, idx; };
// сортировка
sort(queries.begin(), queries.end(), [](const Query& a, const Query& b){
    if (a.l / B != b.l / B) return a.l / B < b.l / B;
    return (a.l / B & 1) ? a.r > b.r : a.r < b.r; // змейка по чётности блока
});

int curL = 0, curR = -1, curAns = 0;
vector<int> cnt(MAXV, 0), a, ans(q);
auto add = [&](int x){ if (cnt[a[x]]++ == 0) curAns++; };
auto rem = [&](int x){ if (--cnt[a[x]] == 0) curAns--; };
for (auto& qu : queries) {
    while (curR < qu.r) add(++curR);
    while (curL > qu.l) add(--curL);
    while (curR > qu.r) rem(curR--);
    while (curL < qu.l) rem(curL++);
    ans[qu.idx] = curAns;
}

Главные условия применимости: запросы оффлайн (можно переупорядочить) и есть дешёвые add/remove за O(1)/O(log). Память O(n + MAXV).