Алгоритм Мо

НЕТ ВОЙНЕ

24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян. Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием. Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей. Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить. Антивоенный комитет России

Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.

meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки.

Алгоритм Мо (англ. 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] a \gt l_i [/math], то будем добавлять в рабочий отрезок элементы слева по одному, пока граница не совпадёт;
• Если же это не так, то есть [math] a \lt l_i [/math] это значит, что в рабочем отрезке присутствуют те элементы, которых там быть не должно, и они должны быть удалены;
• При равенстве [math]a=l_i[/math] никаких действий с левой границей рабочего отрезка производить не потребуется.

Аналогично поступим с [math]b[/math] и [math]r_i[/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]\mathtt{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]O(N + Q_i \cdot K)[/math], где [math]Q_i[/math] — количество запросов, принадлежащих группе под номером [math]i[/math].

Доказательство

Докажем, что на обработку одной группы суммарно уйдёт не больше чем [math]3 \cdot N + Q_i \cdot K[/math] операций [math]\mathtt{add}[/math] и [math]\mathtt{del}[/math].

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

• изначально, до обработки группы, рабочий отрезок был [math][a \ldots b][/math], для обработки первого запроса может потребоваться [math]2 \cdot N[/math] операций [math]\mathtt{add}[/math], [math]\mathtt{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]\mathtt{delLeft}[/math] не будет превосходить [math]K[/math], а суммарно для всей группы — [math]Q_i \cdot K[/math].

Таким образом, нетрудно видеть, все группы будут обработаны за время [math]O \left( \dfrac{N^2}{K} + K \cdot Q \right) [/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)
int a = 1, b = 0 // создаём пустой рабочий отрезок

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 как оператор сравнения
  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() // получаем ответ на [a...b]  

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

Будем использовать код описанный выше, осталось только описать операции [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 \mathtt{cnt[value]}, \mathtt{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].

См. также

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

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

• HackerEarth - Mo's algorithm