Изменения
Нет описания правки
'''Алгоритм Мо''' (англ. ''Mo's algorithm'') — применяется для решения задач, в которых требуется отвечать на запросы <tex>aarr[l \dots ldots r]</tex> на массиве ''без'' изменения элементов и с учётом того, что все запросы известны заранее в оффлайн за время <tex>O(Q \cdot \log{Q} + (N + Q) \cdot \sqrt{N})</tex>, где <tex>Q</tex> {{- --}} количество запросов,а <tex>N</tex> {{--- }} количество элементов в массиве. Характерными примерами задач на этот алгоритм являются: нахождение медианы на отрезке (число, которое встречается больше всех остальных), вычисление количества инверсий на отрезке.
==Алгоритм==
В каждый момент времени поддерживаем структуру данных, в которой хранится некоторый будем хранить непрерывный отрезок <tex>[a \dots 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>[a \dots ldots b]</tex>, а первый необработанный запрос — <tex>[l_i, r_i]</tex> тогда сначала расширим наш рассмотрим случаи: * Если изначально было <tex> a > l_i </tex>, то будем добавлять в рабочий отрезокэлементы слева по одному, пока граница не совпадёт;используя только операции * Если же это не так, то есть <tex>AddLefta < l_i </tex>это значит, что в рабочем отрезке присутствуют те элементы, которых там быть не должно, и они должны быть удалены;* При равенстве <tex>a=l_i</tex> никаких действий с левой границей рабочего отрезка производить не потребуется. Аналогично поступим с <tex>AddRightb</tex> и <tex>r_i</tex>. Для компактности и наглядности кода мы сначала расширим рабочий отрезок до отрезка <tex>[l \dots 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 \dots ldots r_i]</tex>, после чего вызовем <tex>Answer\mathtt{answer}</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>.
==Реализация==
'''int''' K = sqrt(N)
'''int''' a = 1, b = 0 <font color=green>// создаём пустой рабочий отрезок</font>
'''bool''' compareisLess('''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, compareisLess) <font color=green>//сортируем запросы, используя функцию '''compareisLess''' как оператор сравнения</font> '''intfor''' a = 1, b i = 0 <font color=green>//создаём пустой рабочий отрезок</font> '''forto''' i = 0 to Q - 1: '''while''' (a > q[i].l): AddLeftaddLeft(a - 1)
a -= 1
'''while''' (b < q[i].r): AddRightaddRight(b + 1)
b += 1
'''while''' (a < q[i].l): DelLeftdelLeft(a)
a += 1
'''while''' (b > q[i].r): DelRightdelRight(b)
b -= 1
result[q[i].id] = Answeranswer()<font color=green>// получаем ответ на [a...b] </font> Рассмотрим для наглядности решение задачи нахождения моды на отрезке: Будем использовать код описанный выше, осталось только описать операции <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 <font color=green>// находим максимальную пару в множестве</font> Итоговая асимптотика решения: <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] [[Категория: Алгоритмы и структуры данных]][[Категория:Сортировки]][[Категория: Задача о наименьшем общем предке]]