Алгоритм Мо

2021-07-11T09:57:22Z

188.130.155.161:

'''Алгоритм Мо''' (англ. ''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> a < l_i </tex> это значит, что в рабочем отрезке присутствуют те элементы, которых там быть не должно, и они должны быть удалены;
* При равенстве <tex>a=l_i</tex> никаких действий с левой границей рабочего отрезка производить не потребуется.

Аналогично поступим с <tex>b</tex> и <tex>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>3 \cdot N + Q_i \cdot K</tex> операций <tex>\mathtt{add}</tex> и <tex>\mathtt{del}</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>.

==Реализация==
'''struct''' Query:
'''int''' l, r, index

'''int''' K = sqrt(N)
'''int''' a = 1, b = 0 // создаём пустой рабочий отрезок

'''bool''' isLess('''Query''' a, '''Query''' b):
'''if''' a.l / K != b.l / K:
'''return''' a.l < b.l
'''return''' a.r < b.r

'''function''' process('''Query'''[Q] q):
sort(q, isLess) // сортируем запросы, используя функцию '''isLess''' как оператор сравнения
'''for''' i = 0 '''to''' Q - 1:
'''while''' a > q[i].l:
addLeft(a - 1)
a -= 1
'''while''' b < q[i].r:
addRight(b + 1)
b += 1
'''while''' a < q[i].l:
delLeft(a)
a += 1
'''while''' b > q[i].r:
delRight(b)
b -= 1
result[q[i].id] = answer() // получаем ответ на [a...b] 

Рассмотрим для наглядности решение задачи нахождения моды на отрезке:

Будем использовать код описанный выше, осталось только описать операции <tex>\mathtt{addLeft}</tex>, <tex>\mathtt{addRight}</tex>, <tex>\mathtt{delLeft}</tex>, <tex>\mathtt{delRight}</tex>.
Так как в данной задаче порядок чисел на отрезке не важен, важно лишь количество вхождений каждого, то реализация отдельных функций для добавления слева и справа нам не потребуется.

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

'''function''' del('''int''' index):
'''int''' value = arr[index]
current.erase((cnt[value], value))
cnt[a[index]] -= 1
'''if''' cnt[value] > 0:
current.insert((cnt[value], value))

'''function''' answer(): '''int'''
'''return''' current.max.second // находим максимальную пару в множестве

Итоговая асимптотика решения: <tex>O(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/ HackerEarth - Mo's algorithm]

[[Категория: Алгоритмы и структуры данных]]
[[Категория:Сортировки]]
[[Категория: Задача о наименьшем общем предке]]

Викиконспекты - Вклад участника [ru]

Алгоритм Мо