Изменения

'''Алгоритм Мо''' (англ. ''Mo's algorithm'') — применяется для решения задач, в которых требуется отвечать на запросы <tex>aarr[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>AddLeft\mathtt{addLeft(a-1)}</tex>, <tex>AddRight\mathtt{addRight(b+1)}</tex> {{--- }} операции, которые позволяют добавить элемент слева и справа соответственно.* <tex>DelLeft\mathtt{delLeft(a)}</tex>, <tex>DelRight\mathtt{delRight(b)}</tex> {{- --}} операции, которые позволяют удалить элемент слева и справа соответственно.* <tex>Answer\mathtt{answer}</tex> {{--- }} операция, которая позволяет получить ответ на запрос, если бы его границами был рабочий отрезок.

Изначально в качестве рабочего отрезка можно взять любой отрезок. Для удобства чтения будем считать изначальным отрезок <tex>[1;1)</tex>, если не не забытьто есть <tex>a = 1</tex>, <tex>b = 0</tex>, фактически {{---}} пустой отрезок.

Запишем все запросы в массив, некоторым образом их отсортируем и будем их обрабатывать в том порядке, в котором они будут лежать в массиве после [[Сортировки | сортировки]].

используя только операции <tex>AddLeft\mathtt{addLeft}</tex>, <tex>AddRight\mathtt{addRight}</tex> до отрезка <tex>[l \ldots r]</tex>,где <tex>l = \min(a, l_i)</tex>, а <tex>r = \max(b, r_i)</tex>, а затем удалим лишние элементы при помощи операций <tex>DelLeft\mathtt{delLeft}</tex>, <tex>DelRight\mathtt{delRight}</tex>, чтобы получить отрезок <tex>[l_i \ldots r_i]</tex>, после чего вызовем <tex>Answeranswer</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>3 \cdot N + Q_i \cdot K</tex> операций <tex>Addadd</tex> и <tex>Deldel</tex> где <tex>Q_i</tex> {{--- }} количество запросов, принадлежащих группе под номером <tex>i</tex>.

Для доказательства этого давайте рассмотрим отдельно количество сделанных операций каждого из четырёх типов:* Изначально, до обработки группы, рабочий отрезок был <tex>[a \ldots b]</tex>, для обработки первого запроса может потребоваться <tex>2 \cdot N</tex> операций <tex>Addadd</tex>, <tex>Deldel</tex>* <tex>DelRight\mathtt{delRight}</tex> не произойдёт ни разу, т.к. рабочий отрезок будет только расширяться в сторону правого конца* <tex>AddRight\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>AddLeft\mathtt{addLeft}</tex> или <tex>DelLeftdelLeft</tex> также не будет превосходить <tex>K</tex>

При выборе <tex>K = \sqrt{N}</tex> с учётом сортировки по правой границе получается асимптотика времени <tex>O(Q \cdot \log Q + (N + Q) \cdot \sqrt N)</tex>

'''bool''' compareisLess('''Query''' a, '''Query''' b):

sort(q, compareisLess) <font color=green>//сортируем запросы, используя функцию '''compareisLess''' как оператор сравнения</font> '''int''' a = 1, b = 0 <font color=green>//создаём пустой рабочий отрезок</font>

'''while''' (a > q[i].l): AddLeftaddLeft(a - 1)

'''while''' (b < q[i].r): AddRightaddRight(b + 1)

'''while''' (a < q[i].l): DelLeftdelLeft(a)

'''while''' (b > q[i].r): DelRightdelRight(b)

result[q[i].id] = Answeranswer()

Будем использовать код описанный выше, осталось только описать операции <tex>AddLeft\mathtt{addLeft}</tex>, <tex>AddRight\mathtt{addRight}</tex>, <tex>DelLeft\mathtt{delLeft}</tex>, <tex>DelRight\mathtt{delRight}</tex>.

Для простоты будем считать, что все числа '''не превышают <tex>N</tex>''', тогда будем хранить массив <tex>cnt[N + 1]</tex>, где <tex>cnt[value]</tex> - количество вхождений числа <tex>value</tex> в рабочем отрезке. Будем помимо этого массива хранить отсортированное множество <tex>current</tex>, в котором будут содержаться все пары вида <tex>\langle cnt[value], value \rangle</tex>, для ненулевых <tex>cnt[value]</tex>. Реализовать его можно, например, используя [[Красно-черное_дерево | Красно-черное дерево]] Тогда операции будут иметь следующий вид: '''function''' Addadd('''int''' index): '''int''' value = aarr[index]

'''function''' Deldel('''int''' index): '''int''' value = aarr[index]

'''function''' Answeranswer(): '''int''' '''return <tex>\''' current.max(current).second</tex> <font color=green>//В данном случае просто требуется вернуть второй элемент из максимальной пары из текущего состояния массива находим максимальную пару в множестве</font> Итоговая асимптотика решения: <tex>currentO(Q \cdot \log Q + (N + Q) \cdot \sqrt{N} \cdot \log N)</tex>< == См. также ==* [[Статистики_на_отрезках._Корневая_эвристика | Корневая эвристика]]* [[Решение_RMQ_с_помощью_разреженной_таблицы#.D0.A0.D0.B0.D0.B7.D1.80.D0.B5.D0.B6.D0.B5.D0.BD.D0.BD.D0.B0.D1.8F_.D1.82.D0.B0.D0.B1.D0.BB.D0.B8.D1.86.D0.B0 | Разреженная таблица]] ==Источники информации==* [https://www.hackerearth.com/practice/notes/mos-algorithm/font>Mo's algorithm]