Алгоритм Мо
Алгоритм Мо (англ. Mo's algorithm) — применяется для решения задач, в которых требуется отвечать на запросы на массиве без изменения элементов в оффлайн за время , где — количество запросов, а — количество элементов в массиве. Характерными примерами задач на этот алгоритм являются: нахождение моды на отрезке (число, которое встречается больше всех остальных), вычисление количества инверсий на отрезке.
Алгоритм
В каждый момент времени будем хранить непрерывный отрезок исходного массива (будем называть его рабочим отрезком), вместе со структурой данных, которая умеет обрабатывать следующие операции:
- , — операции, которые позволяют добавить элемент в рабочий отрезок слева и справа соответственно;
- , — операции, которые позволяют удалить элемент рабочего отрезка слева и справа соответственно;
- — операция, которая позволяет получить ответ на запрос, если бы его границами был рабочий отрезок.
Изначально в качестве рабочего отрезка можно взять любой отрезок. Для удобства чтения будем считать изначальным отрезок , то есть , , фактически — пустой отрезок.
Запишем все запросы в массив, отсортируем их определённым способом (который будет описан ниже) будем их обрабатывать в том порядке, в котором они будут лежать в массиве после сортировки.
Допустим, что текущий рабочий отрезок — , а первый необработанный запрос — тогда рассмотрим случаи:
- Если изначально было , то будем добавлять в рабочий отрезок элементы слева по одному, пока граница не совпадёт;
- Если же это не так, то есть это значит, что в рабочем отрезке присутствуют те элементы, которых там быть не должно, и они должны быть удалены;
- При равенстве никаких действий с левой границей рабочего отрезка производить не потребуется.
Аналогично поступим с и . Для компактности и наглядности кода мы сначала расширим рабочий отрезок до отрезка , где , а , а затем удалим лишние элементы при помощи операций , , чтобы получить отрезок , после чего вызовем и запомним ответ для этого запроса.
Теперь разберём поподробнее, как именно следует сортировать запросы для достижения вышеназванной асимптотики по времени.
Разделим все запросы на блоки размера по левой границе: те запросы, для которых — попадают в первую группу, те запросы, для которых — во вторую, — в третью, и так далее. Будем рассматривать все группы запросов независимо друг от друга. Если внутри каждой группы отсортировать запросы увеличению правой границы, то асимптотика по времени для обработки одной группы будет , где — количество запросов, принадлежащих группе под номером .
Доказательство
Докажем, что на обработку одной группы суммарно уйдёт не больше чем операций и .
Для этого рассмотрим отдельно количество сделанных операций каждого из четырёх типов:
- изначально, до обработки группы, рабочий отрезок был , для обработки первого запроса может потребоваться операций , ;
- между отрезками одной группы не произойдёт ни разу, так как рабочий отрезок внутри одной группы будет только расширяться в сторону правого конца;
- в этой группе произойдёт суммарно не больше чем раз, так как минимальная правая граница — , а максимальная — ;
- для оставшихся двух операций рассмотрим два последовательных запроса , . Нетрудно заметить, что так как отрезки принадлежат одной группе, то , следовательно, количество операций или не будет превосходить , а суммарно для всей группы — .
Таким образом, нетрудно видеть, все группы будут обработаны за время .
При выборе с учётом сортировки по правой границе получается асимптотика времени .
Реализация
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]
Рассмотрим для наглядности решение задачи нахождения моды на отрезке:
Будем использовать код описанный выше, осталось только описать операции , , , . Так как в данной задаче порядок чисел на отрезке не важен, важно лишь количество вхождений каждого, то реализация отдельных функций для добавления слева и справа нам не потребуется.
Для простоты будем считать, что все числа не превышают , тогда будем хранить массив , где - количество вхождений числа в рабочем отрезке. Будем помимо этого массива хранить отсортированное множество , в котором будут содержаться все пары вида , для ненулевых . Реализовать его можно, например, используя красно-черное дерево Тогда операции будут иметь следующий вид:
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 // находим максимальную пару в множестве
Итоговая асимптотика решения: .
