Алгоритм Мо

Алгоритм Мо (англ. 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
    while (b < q[i].r):
      AddRight()
      b += 1
    while (a < q[i].l):
      DelLeft()
      a += 1
    while (b > q[i].r):
      DelRight()
      b -= 1
    result[q[i].id] = Answer()