Изменения
Нет описания правки
'''Алгоритм Мо''' (англ. ''Mo's algorithm'') — применяется для решения задач, в которых требуется отвечать на запросы <tex>arr[l \ldots r]</tex> на массиве
''без'' изменения элементов в оффлайн за время <tex>O(Q \cdot \log{Q} + (N + Q) \cdot \sqrt{N})</tex>, где <tex>Q</tex> {{---}} количество запросов,
а <tex>N</tex> {{---}} количество элементов в массиве. Характерными примерами задач на этот алгоритм являются: нахождение моды медианы на отрезке (число, которое встречается больше всех остальных),
вычисление количества инверсий на отрезке.
В каждый момент времени будем хранить непрерывный отрезок <tex>[a \ldots b]</tex> исходного массива (будем называть его рабочим отрезком), вместе со структурой данных,
которая умеет обрабатывать следующие операции:
* <tex>\mathtt{addLeft(a-1)}</tex>, <tex>\mathtt{addRight(b+1)}</tex> {{---}} операции, которые позволяют добавить элемент в рабочий отрезок слева и справа соответственно.;* <tex>\mathtt{delLeft(a)}</tex>, <tex>\mathtt{delRight(b)}</tex> {{---}} операции, которые позволяют удалить элемент рабочего отрезка слева и справа соответственно.;* <tex>\mathtt{answer}</tex> {{---}} операция, которая позволяет получить ответ на запрос, если бы его границами был рабочий отрезок;.
Изначально в качестве рабочего отрезка можно взять любой отрезок. Для удобства чтения будем считать изначальным отрезок <tex>[1;1)</tex>, то есть <tex>a = 1</tex>, <tex>b = 0</tex>, фактически {{---}} пустой отрезок.
Запишем все запросы в массив, некоторым образом отсортируем их отсортируем и определённым способом (который будет описан ниже) будем их обрабатывать в том порядке, в котором они будут лежать в массиве после [[Сортировки | сортировки]].
Допустим, что текущий рабочий отрезок — <tex>[a \ldots b]</tex>, а первый необработанный запрос — <tex>[l_i, r_i]</tex> тогда сначала расширим наш рассмотрим случаи: * Если изначально было <tex> a > l_i </tex>, то будем добавлять в рабочий отрезокэлементы слева по одному, пока граница не совпадёт;используя только операции * Если же это не так, то есть <tex>\mathtt{addLeft}a < l_i </tex>это значит, что в рабочем отрезке присутствуют те элементы, которых там быть не должно, и они должны быть удалены;* При равенстве <tex>a=l_i</tex> никаких действий с левой границей рабочего отрезка производить не потребуется. Аналогично поступим с <tex>b</tex> и <tex>\mathtt{addRight}r_i</tex> . Для компактности и наглядности кода мы сначала расширим рабочий отрезок до отрезка <tex>[l \ldots r]</tex>,где <tex>l = \min(a, l_i)</tex>, а <tex>r = \max(b, r_i)</tex>, а затем удалим лишние элементы при помощи операций <tex>\mathtt{delLeft}</tex>, <tex>\mathtt{delRight}</tex>, чтобы получить отрезок <tex>[l_i \ldots r_i]</tex>, после чего вызовем <tex>\mathtt{answer}</tex> и запомним ответ для этого запроса.
Теперь разберём поподробнее, как именно следует сортировать запросы для достижения вышеназванной асимптотики по времени.
Разделим все запросы на блоки размера <tex>K</tex> по левой границе: те запросы, для которых <tex>1 \leqslant l_i \leqslant K</tex> {{---}} попадают в первую группу,
те запросы, для которых <tex>K + 1 \leqslant l_i \leqslant 2 \cdot K</tex> {{---}} во вторую, <tex>2 \cdot K + 1 \leqslant l_i \leqslant 3 \cdot K</tex> {{---}} в третью, и так далее. Будем рассматривать все группы запросов независимо друг от друга. Если внутри каждой группы отсортировать запросы увеличению правой границы, то асимптотика по времени для обработки одной группы будет <tex>O(N + Q_i \cdot K)</tex>, где <tex>Q_i</tex> {{---}} количество запросов, принадлежащих группе под номером <tex>i</tex>.
==Доказательство==
Для этого рассмотрим отдельно количество сделанных операций каждого из четырёх типов:
* изначально, до обработки группы, рабочий отрезок был <tex>[a \ldots b]</tex>, для обработки первого запроса может потребоваться <tex>2 \cdot N</tex> операций <tex>\mathtt{add}</tex>, <tex>\mathtt{del}</tex>;* <tex>\mathtt{delRight}</tex> между отрезками одной группы не произойдёт ни разу, так как рабочий отрезок внутри одной группы будет только расширяться в сторону правого конца;* <tex>\mathtt{addRight}</tex> в этой группе произойдёт суммарно не больше чем <tex>N</tex> раз, так как минимальная правая граница {{---}} <tex>1</tex>, а максимальная {{---}} <tex>N</tex>;* для оставшихся двух операций рассмотрим два последовательных запроса <tex>[l_i \ldots r_i]</tex>, <tex>[l_j \ldots r_j]</tex>. Нетрудно заметить, что так как отрезки принадлежат одной группе, то <tex>|l_i - l_j| < K</tex>, следовательно, количество операций <tex>\mathtt{addLeft}</tex> или <tex>\mathtt{delLeft}</tex> не будет превосходить <tex>K</tex>, а суммарно для всей группы {{---}} <tex>Q_i \cdot K</tex>;.
Таким образом, нетрудно видеть, все группы будут обработаны за время <tex>O \left( \dfrac{N^2}{K} + K \cdot Q \right) </tex>.
При выборе <tex>K = \sqrt{N}</tex> с учётом сортировки по правой границе получается асимптотика времени <tex>O(Q \cdot \log Q + (N + Q) \cdot \sqrt N)</tex>.
==Реализация==
'''return''' current.max.second <font color=green>// находим максимальную пару в множестве</font>
Итоговая асимптотика решения: <tex>O(Q \cdot \log Q + (N + Q) \cdot \sqrt{N} \cdot \log N)</tex>.
== См. также ==
