17
правок
Изменения
Нет описания правки
'''Алгоритм Мо''' (англ. ''Mo's algorithm'') — применяется для решения задач, в которых требуется отвечать на запросы <tex>a[l \dots r]</tex> на массиве
''без'' изменения элементов и с учётом того, что все запросы известны заранее в оффлайн за время <tex>O(Q \cdot \log{Q} + (N + Q) \cdot \sqrt{N})</tex>, где <tex>Q</tex> - количество запросов,а <tex>N</tex> - количество элементов в массиве. Характерными примерами задач на этот алгоритм являются: нахождение моды на отрезке (число, которое встречается больше всех остальных), вычисление количества инверсий на отрезке.
==Алгоритм==
'''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()
Рассмотрим для наглядности решение задачи нахождения моды на отрезке:
Будем использовать код описанный выше, осталось только описать операции <tex>AddLeft</tex>, <tex>AddRight</tex>, <tex>DelLeft</tex>, <tex>DelRight</tex>.
Так как в данной задаче порядок чисел на отрезке не важен, важно лишь количество вхождений каждого, то реализация отдельных функций для добавления слева и справа нам не потребуется.
Для простоты будем считать, что все числа '''не превышают <tex>N</tex>''', тогда будем хранить массив <tex>cnt[N + 1]</tex>, где <tex>cnt[value]</tex> - количество вхождений числа <tex>value</tex> в рабочем отрезке. Тогда операции будут иметь следующий вид:
'''function''' Add('''int''' index):
cnt[a[index]] += 1
update_best()
'''function''' Del('''int''' index):
cnt[a[index]] -= 1
update_best()
В данном случае реализовать '''update_best''' будет проще всего используя <tex>TreeSet</tex> или его аналоги из стандартной библиотеки языка. Стоит отметить, что это добавляет множитель <tex>O(\log N)</tex> в асимптотике. Итоговая асимптотика тогда <tex>O(Q \cdot \log{Q} + (N + Q) \cdot \sqrt{N} \cdot \log N)</tex>
