3-Д мо
Оказывается, если очень захотеть, алгоритм Мо можно применять и в задачах, где надо обрабатывать запросы обновления. Введем третий параметр `get`-запроса -- t, который будет равен числу `update`-запросов до текущего `get`. Снова пересортируем `get`-запросы, но в этот раз в порядке $(\frac{t}{n^\frac{2}{3}}, \frac{l}{n^\frac{2}{3}}, r)$. После чего оставим такой же [алгоритм Мо], как и раньше, только в трех измерениях. Единственное что -- теперь при переключении между версиями массива надо будет менять ровно один элемент, и иногда менять его в структуре, если он принадлежал текущему отрезку.
Время работы нового алгоритма будет $O(n^\frac{5}{3})$, что доказывается аналогично обычному Мо.
Автор конспекта: Константин Амеличев
По всем вопросам пишите в telegram @kik0s