Алгоритм Мо

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

Алгоритм

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

• [math]\mathtt{addLeft(a-1)}[/math], [math]\mathtt{addRight(b+1)}[/math] — операции, которые позволяют добавить элемент слева и справа соответственно.
• [math]\mathtt{delLeft(a)}[/math], [math]\mathtt{delRight(b)}[/math] — операции, которые позволяют удалить элемент слева и справа соответственно.
• [math]\mathtt{answer}[/math] — операция, которая позволяет получить ответ на запрос, если бы его границами был рабочий отрезок.

Изначально в качестве рабочего отрезка можно взять любой отрезок. Для удобства чтения будем считать изначальным отрезок [math][1;1)[/math], то есть [math]a = 1[/math], [math]b = 0[/math], фактически — пустой отрезок.

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

Допустим, что текущий рабочий отрезок — [math][a \ldots b][/math], а первый необработанный запрос — [math][l_i, r_i][/math] тогда сначала расширим наш отрезок, используя только операции [math]\mathtt{addLeft}[/math], [math]\mathtt{addRight}[/math] до отрезка [math][l \ldots r][/math], где [math]l = \min(a, l_i)[/math], а [math]r = \max(b, r_i)[/math], а затем удалим лишние элементы при помощи операций [math]\mathtt{delLeft}[/math], [math]\mathtt{delRight}[/math], чтобы получить отрезок [math][l_i \ldots r_i][/math], после чего вызовем [math]answer[/math] и запомним ответ для этого запроса.

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

Разделим все запросы на блоки размера [math]K[/math] по левой границе: те запросы, для которых [math]1 \leqslant l_i \leqslant K[/math] — попадают в первую группу, те запросы, для которых [math]K + 1 \leqslant l_i \leqslant 2 \cdot K[/math] — во вторую, [math]2 \cdot K + 1 \leqslant l_i \leqslant 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 \ldots b][/math], для обработки первого запроса может потребоваться [math]2 \cdot N[/math] операций [math]add[/math], [math]del[/math]
• [math]\mathtt{delRight}[/math] не произойдёт ни разу, т.к. рабочий отрезок будет только расширяться в сторону правого конца
• [math]\mathtt{addRight}[/math] произойдёт суммарно не больше чем [math]N[/math] раз, так как минимальная правая граница — [math]1[/math], а максимальная — [math]N[/math]
• Для оставшихся двух операций рассмотрим два последовательных запроса [math][l_i \ldots r_i][/math], [math][l_j \ldots r_j][/math]. Нетрудно заметить, что так как отрезки принадлежат одной группе, то [math]|l_i - l_j| \lt K[/math], следовательно, количество операций [math]\mathtt{addLeft}[/math] или [math]delLeft[/math] также не будет превосходить [math]K[/math]

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

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

Реализация

struct Query:
  int l, r, index 

int K = sqrt(N)

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 как оператор сравнения
  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]\mathtt{addLeft}[/math], [math]\mathtt{addRight}[/math], [math]\mathtt{delLeft}[/math], [math]\mathtt{delRight}[/math]. Так как в данной задаче порядок чисел на отрезке не важен, важно лишь количество вхождений каждого, то реализация отдельных функций для добавления слева и справа нам не потребуется.

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

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 // находим максимальную пару в множестве

Итоговая асимптотика решения: [math]O(Q \cdot \log Q + (N + Q) \cdot \sqrt{N} \cdot \log N)[/math]

См. также

• Корневая эвристика
• Разреженная таблица

Источники информации

• Mo's algorithm