Алгоритм Мо

Если запросы можно прочитать заранее, их выгодно переставить. Тогда границы окна суммарно проходят корень от n на запрос.

3 мин

Иногда сводку блока посчитать нельзя: вопрос вроде «сколько различных чисел на отрезке» не складывается из ответов для кусков.

Зато почти всегда легко подвинуть границу на единицу: добавить или убрать один элемент и поправить ответ. Это и есть условие применимости алгоритма Мо.

Идея

Пусть все запросы известны заранее - алгоритм офлайновый. Держим текущее окно $[l, r]$ и его ответ; переходя к следующему запросу, двигаем границы по одной.

Стоимость - суммарное число сдвигов. Если отвечать в порядке поступления, оно может быть $O(nq)$ . Но запросы можно переставить.

Порядок Мо: сортируем запросы по номеру блока левой границы, а внутри блока - по правой границе.

std::sort(queries.begin(), queries.end(), [&](auto &x, auto &y) {
    int bx = x.l / B, by = y.l / B;
    if (bx != by) return bx < by;
    return x.r < y.r;
});

Тогда левая граница внутри блока гуляет не дальше $B$ на запрос - это $O(qB)$ суммарно. Правая внутри блока только растёт - это $O(n)$ на блок, то есть $O(n \cdot n / B)$ всего.

Сумма $qB + n^2/B$ минимальна при $B = n / \sqrt{q}$ , и тогда всё вместе - $O((n + q)\sqrt{n})$ .

Змейка

Есть дешёвое улучшение: в блоках с нечётным номером сортировать по правой границе по убыванию. Тогда правая граница не отматывается в начало при переходе к следующему блоку, а идёт обратно.

if (bx & 1) return x.r > y.r;

Измерено число перемещений указателей на случайных запросах:

$n$	запросов	обычный порядок	змейкой	оценка $(n+q)\sqrt{n}$
10 000	10 000	1 311 638	839 562	2 000 000
10 000	100 000	4 233 335	2 647 797	11 000 000
100 000	10 000	13 114 839	8 367 087	34 760 000
100 000	100 000	41 955 884	26 413 719	63 200 000

Змейка стабильно экономит около 36 процентов - на всех четырёх размерах отношение получилось 0,63-0,64. Это одна строчка в компараторе, и она того стоит.

Заодно видно, что реальное число сдвигов заметно меньше теоретической оценки: примерно две трети от неё в обычном порядке.

Чего Мо не умеет

Не работает онлайн. Все запросы должны быть известны заранее. Если задача интерактивная или ответ на запрос влияет на следующий - приём неприменим.

Не любит дорогое перемещение. Если добавление элемента стоит $O(\log n)$ , общая цена становится $O((n+q)\sqrt{n}\log n)$ , и это обычно уже слишком.

Плохо дружит с обновлениями. Есть вариант с изменениями - «Мо по трём координатам» с оценкой $O(n^{5/3})$ , - но он заметно сложнее и нужен редко.

Зато там, где Мо применим, он обычно самый короткий из возможных способов.