Алгоритм Мо
Пусть есть задача на массиве, которую мы решаем без запросов обновления, в offline. Запросы могут быть любой степени ужасности, если мы умеем на них отвечать структурой данных, которая хранит информацию об отрезке $[l, r]$ и поддерживает следующие операции:
- add_left
- add_right
- del_left
- del_right
- query
Которые меняют границы отрезка и внутреннюю структуру данных, а также позволяют сделать запрос. Все запросы мы пересортируем. Теперь они будут отсортированы по паре $(\lfloor \sqrt{l} \rfloor, r)$. Отвечать на запрос мы будем таким образом --- с помощщью реализованных операций подстроим необходимые нам границы отрезка, после чего вызовем $query$.
Оценим время выполнения. Заметим, что левые границы разбиваются по блокам, а внутри запросов одного блока правые границы отсортированы. При переходе от запроса к запросу внутри блока, левая граница делает $O(\sqrt n)$ сдвигов. Правая же граница для запросов одного блока суммарно сделает $O(n)$ сдвигов. Так как число блоков $O(\sqrt n)$, то и суммарное время работы $O(\sqrt n)$.
Автор конспекта: Константин Амеличев
По всем вопросам пишите в telegram @kik0s