Алгоритм Мо — различия между версиями
Noobgam (обсуждение | вклад) |
Noobgam (обсуждение | вклад) |
||
| Строка 95: | Строка 95: | ||
* [https://www.hackerearth.com/practice/notes/mos-algorithm/ HackerEarth - Mo's algorithm] | * [https://www.hackerearth.com/practice/notes/mos-algorithm/ HackerEarth - Mo's algorithm] | ||
| + | [[Категория: Алгоритмы и структуры данных]] | ||
[[Категория:Сортировки]] | [[Категория:Сортировки]] | ||
| − | [[Категория: | + | [[Категория: Задача о наименьшем общем предке]] |
Версия 23:22, 15 января 2017
Алгоритм Мо (англ. 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 // находим максимальную пару в множестве
Итоговая асимптотика решения:
