Изменения
Нет описания правки
'''Алгоритм Мо''' (англ. ''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>AddLeft\mathtt{addLeft}</tex>, <tex>AddRight\mathtt{addRight}</tex>, <tex>DelLeft\mathtt{delLeft}</tex>, <tex>DelRight\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''' Addadd('''int''' index): '''int''' value = arr[index] '''if''' cnt[value] > 0: current.erase((cnt[value], value))
cnt[a[index]] += 1
cnt[a[index]] -= 1
