Алгоритм Мо

Алгоритм Мо (англ. Mo's algorithm) — применяется для решения задач, в которых требуется отвечать на запросы [math]a[l \dots r][/math] на массиве без изменения элементов в оффлайн за время [math]O(Q \cdot \log{Q} + (N + Q) \cdot \sqrt{N})[/math], где [math]Q[/math] - количество запросов, а [math]N[/math] - количество элементов в массиве. Характерными примерами задач на этот алгоритм являются: нахождение моды на отрезке (число, которое встречается больше всех остальных), вычисление количества инверсий на отрезке.

Алгоритм

В каждый момент времени поддерживаем структуру данных, в которой хранится некоторый непрерывный отрезок [math][a \dots b][/math] исходного массива (будем называть его рабочим отрезком), которая поддерживает следующие операции:

• [math]AddLeft[/math], [math]AddRight[/math] - операции, которые позволяют добавить элемент слева и справа соответственно.
• [math]DelLeft[/math], [math]DelRight[/math] - операции, которые позволяют удалить элемент слева и справа соответственно.
• [math]Answer[/math] - операция, которая позволяет получить ответ на запрос, если бы его границами был рабочий отрезок.

Изначально в качестве рабочего отрезка можно взять любой отрезок, если не не забыть

Запишем все запросы в массив, некоторым образом их отсортируем и будем их обрабатывать в том порядке, в котором они будут лежать в массиве после сортировки.

Допустим, что текущий рабочий отрезок — [math][a \dots b][/math], а первый необработанный запрос — [math][l_i, r_i][/math] тогда сначала расширим наш отрезок, используя только операции [math]AddLeft[/math], [math]AddRight[/math] до отрезка [math][l \dots r][/math], где [math]l = min(a, l_i)[/math], а [math]r = max(b, r_i)[/math], а затем удалим лишние элементы при помощи операций [math]DelLeft[/math], [math]DelRight[/math], чтобы получить отрезок [math][l_i \dots r_i][/math], после чего вызовем [math]Answer[/math] и запомним ответ для этого запроса.

Теперь разберём поподробнее, как именно следует сортировать запросы для достижения вышеназванной асимптотики по времени.

Давайте разделим все запросы на блоки размера [math]K[/math] по левой границе: те запросы, для которых [math]1 \le l_i \le K[/math] - попадают в первую группу, те запросы, для которых [math]K + 1 \le l_i \le 2 \cdot K[/math] - во вторую, [math]2 \cdot K + 1 \le l_i \le 3 \cdot K[/math] - в третью, и так далее. Будем рассматривать все группы запросов независимо друг от друга. Если внутри каждой группы отсортировать запросы по правой границе, будет нетрудно заметить, что для всей группы суммарно будет выполнено не больше чем [math]3 \cdot N + Q_i \cdot K[/math] операций [math]Add[/math] и [math]Del[/math] где [math]Q_i[/math] - количество запросов, принадлежащих группе под номером [math]i[/math].

Для доказательства этого давайте рассмотрим отдельно количество сделанных операций каждого из четырёх типов:

• Изначально, до обработки группы, рабочий отрезок был [math][a \dots b][/math], для обработки первого запроса может потребоваться [math]2 \cdot N[/math] операций [math]Add[/math], [math]Del[/math]
• [math]DelRight[/math] не произойдёт ни разу, т.к. рабочий отрезок будет только расширяться в сторону правого конца
• [math]AddRight[/math] произойдёт суммарно не больше чем [math]N[/math] раз, так как минимальная правая граница - [math]1[/math], а максимальная - [math]N[/math]
• Для оставшихся двух операций рассмотрим два последовательных запроса [math][l_i \dots r_i][/math], [math][l_j \dots r_j][/math]. Нетрудно заметить, что так как отрезки принадлежат одной группе, то [math]|l_i - l_j| \lt K[/math], следовательно, количество операций [math]AddLeft[/math] или [math]DelLeft[/math] также не будет превосходить [math]K[/math]

Таким образом, нетрудно видеть, все группы будут обработаны за время [math]O(\frac{N^2}{K} + K \cdot Q)[/math].

При выборе [math]K = \sqrt{N}[/math] с учётом сортировки по правой границе получается асимптотика времени [math]O(Q \log Q + (N + Q) \cdot \sqrt N)[/math]

Реализация

struct Query:
  int l, r, index 

int K = sqrt(N)

bool compare(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, compare) //сортируем запросы, используя функцию compare как оператор сравнения
  int a = 1, b = 0 //создаём пустой рабочий отрезок
  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()

Рассмотрим для наглядности решение задачи нахождения моды на отрезке:

Будем использовать код описанный выше, осталось только описать операции [math]AddLeft[/math], [math]AddRight[/math], [math]DelLeft[/math], [math]DelRight[/math]. Так как в данной задаче порядок чисел на отрезке не важен, важно лишь количество вхождений каждого, то реализация отдельных функций для добавления слева и справа нам не потребуется.

Для простоты будем считать, что все числа не превышают [math]N[/math], тогда будем хранить массив [math]cnt[N + 1][/math], где [math]cnt[value][/math] - количество вхождений числа [math]value[/math] в рабочем отрезке. Тогда операции будут иметь следующий вид:

function Add(int index):
  cnt[a[index]] += 1
  update_best()

 function Del(int index):
  cnt[a[index]] -= 1
  update_best()

В данном случае реализовать update_best будет проще всего используя [math]TreeSet[/math] или его аналоги из стандартной библиотеки языка. Стоит отметить, что это добавляет множитель [math]O(\log N)[/math] в асимптотике. Итоговая асимптотика тогда [math]O(Q \cdot \log{Q} + (N + Q) \cdot \sqrt{N} \cdot \log N)[/math]