Алгоритм Мо

Пусть есть задача на массиве, которую мы решаем без запросов обновления, в 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