Алгоритм Мо — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(не показано 5 промежуточных версий 1 участника)
Строка 1: Строка 1:
 
'''Алгоритм Мо''' (англ. ''Mo's algorithm'') — применяется для решения задач, в которых требуется отвечать на запросы <tex>arr[l \ldots r]</tex> на массиве  
 
'''Алгоритм Мо''' (англ. ''Mo's algorithm'') — применяется для решения задач, в которых требуется отвечать на запросы <tex>arr[l \ldots r]</tex> на массиве  
 
''без'' изменения элементов в оффлайн за время <tex>O(Q \cdot \log{Q} + (N + Q) \cdot \sqrt{N})</tex>, где <tex>Q</tex> {{---}} количество запросов,
 
''без'' изменения элементов в оффлайн за время <tex>O(Q \cdot \log{Q} + (N + Q) \cdot \sqrt{N})</tex>, где <tex>Q</tex> {{---}} количество запросов,
а <tex>N</tex> {{---}} количество элементов в массиве. Характерными примерами задач на этот алгоритм являются: нахождение моды на отрезке (число, которое встречается больше всех остальных),  
+
а <tex>N</tex> {{---}} количество элементов в массиве. Характерными примерами задач на этот алгоритм являются: нахождение медианы на отрезке (число, которое встречается больше всех остальных),  
 
вычисление количества инверсий на отрезке.  
 
вычисление количества инверсий на отрезке.  
  
Строка 7: Строка 7:
 
В каждый момент времени будем хранить непрерывный отрезок <tex>[a \ldots b]</tex> исходного массива (будем называть его рабочим отрезком), вместе со структурой данных,  
 
В каждый момент времени будем хранить непрерывный отрезок <tex>[a \ldots b]</tex> исходного массива (будем называть его рабочим отрезком), вместе со структурой данных,  
 
которая умеет обрабатывать следующие операции:
 
которая умеет обрабатывать следующие операции:
* <tex>\mathtt{addLeft(a-1)}</tex>, <tex>\mathtt{addRight(b+1)}</tex> {{---}} операции, которые позволяют добавить элемент в рабочий отрезок слева и справа соответственно.
+
* <tex>\mathtt{addLeft(a-1)}</tex>, <tex>\mathtt{addRight(b+1)}</tex> {{---}} операции, которые позволяют добавить элемент в рабочий отрезок слева и справа соответственно;
* <tex>\mathtt{delLeft(a)}</tex>, <tex>\mathtt{delRight(b)}</tex> {{---}} операции, которые позволяют удалить элемент рабочего отрезка слева и справа соответственно.
+
* <tex>\mathtt{delLeft(a)}</tex>, <tex>\mathtt{delRight(b)}</tex> {{---}} операции, которые позволяют удалить элемент рабочего отрезка слева и справа соответственно;
* <tex>\mathtt{answer}</tex> {{---}} операция, которая позволяет получить ответ на запрос, если бы его границами был рабочий отрезок;
+
* <tex>\mathtt{answer}</tex> {{---}} операция, которая позволяет получить ответ на запрос, если бы его границами был рабочий отрезок.
  
 
Изначально в качестве рабочего отрезка можно взять любой отрезок. Для удобства чтения будем считать изначальным отрезок <tex>[1;1)</tex>, то есть <tex>a = 1</tex>, <tex>b = 0</tex>, фактически {{---}} пустой отрезок.
 
Изначально в качестве рабочего отрезка можно взять любой отрезок. Для удобства чтения будем считать изначальным отрезок <tex>[1;1)</tex>, то есть <tex>a = 1</tex>, <tex>b = 0</tex>, фактически {{---}} пустой отрезок.
  
Запишем все запросы в массив, некоторым образом их отсортируем и будем их обрабатывать в том порядке, в котором они будут лежать в массиве после [[Сортировки | сортировки]].
+
Запишем все запросы в массив, отсортируем их определённым способом (который будет описан ниже) будем их обрабатывать в том порядке, в котором они будут лежать в массиве после [[Сортировки | сортировки]].
  
Допустим, что текущий рабочий отрезок — <tex>[a \ldots b]</tex>, а первый необработанный запрос — <tex>[l_i, r_i]</tex> тогда сначала расширим наш отрезок,  
+
Допустим, что текущий рабочий отрезок — <tex>[a \ldots b]</tex>, а первый необработанный запрос — <tex>[l_i, r_i]</tex> тогда рассмотрим случаи:
используя только операции <tex>\mathtt{addLeft}</tex>, <tex>\mathtt{addRight}</tex> до отрезка <tex>[l \ldots r]</tex>,
+
* Если изначально было <tex> a > l_i </tex>, то будем добавлять в рабочий отрезок элементы слева по одному, пока граница не совпадёт;
где <tex>l = \min(a, l_i)</tex>, а <tex>r = \max(b, r_i)</tex>, а затем удалим лишние элементы при помощи операций <tex>\mathtt{delLeft}</tex>, <tex>\mathtt{delRight}</tex>, чтобы получить отрезок <tex>[l_i \ldots r_i]</tex>, после чего вызовем <tex>\mathtt{answer}</tex> и запомним ответ для этого запроса.
+
* Если же это не так, то есть <tex> a < l_i </tex> это значит, что в рабочем отрезке присутствуют те элементы, которых там быть не должно, и они должны быть удалены;
 +
* При равенстве <tex>a=l_i</tex> никаких действий с левой границей рабочего отрезка производить не потребуется.
 +
 
 +
Аналогично поступим с <tex>b</tex> и <tex>r_i</tex>. Для компактности и наглядности кода мы сначала расширим рабочий отрезок до отрезка <tex>[l \ldots r]</tex>, где <tex>l = \min(a, l_i)</tex>, а <tex>r = \max(b, r_i)</tex>, а затем удалим лишние элементы при помощи операций <tex>\mathtt{delLeft}</tex>, <tex>\mathtt{delRight}</tex>, чтобы получить отрезок <tex>[l_i \ldots r_i]</tex>, после чего вызовем <tex>\mathtt{answer}</tex> и запомним ответ для этого запроса.
  
 
Теперь разберём поподробнее, как именно следует сортировать запросы для достижения вышеназванной асимптотики по времени.
 
Теперь разберём поподробнее, как именно следует сортировать запросы для достижения вышеназванной асимптотики по времени.
  
 
Разделим все запросы на блоки размера <tex>K</tex> по левой границе: те запросы, для которых <tex>1 \leqslant l_i \leqslant K</tex> {{---}} попадают в первую группу,  
 
Разделим все запросы на блоки размера <tex>K</tex> по левой границе: те запросы, для которых <tex>1 \leqslant l_i \leqslant K</tex> {{---}} попадают в первую группу,  
те запросы, для которых <tex>K + 1 \leqslant l_i \leqslant 2 \cdot K</tex> {{---}} во вторую, <tex>2 \cdot K + 1 \leqslant l_i \leqslant 3 \cdot K</tex> {{---}} в третью, и так далее. Будем рассматривать все группы запросов независимо друг от друга. Если внутри каждой группы отсортировать запросы увеличению правой границы, то асимптотика по времени для обработки одной группы будет <tex>O(N + Q_i \cdot K)</tex>, где <tex>Q_i</tex> {{---}} количество запросов, принадлежащих группе под номером <tex>i</tex>.  
+
те запросы, для которых <tex>K + 1 \leqslant l_i \leqslant 2 \cdot K</tex> {{---}} во вторую, <tex>2 \cdot K + 1 \leqslant l_i \leqslant 3 \cdot K</tex> {{---}} в третью, и так далее. Будем рассматривать все группы запросов независимо друг от друга. Если внутри каждой группы отсортировать запросы увеличению правой границы, то асимптотика по времени для обработки одной группы будет <tex>O(N + Q_i \cdot K)</tex>, где <tex>Q_i</tex> {{---}} количество запросов, принадлежащих группе под номером <tex>i</tex>.
  
 
==Доказательство==
 
==Доказательство==
Строка 28: Строка 31:
  
 
Для этого рассмотрим отдельно количество сделанных операций каждого из четырёх типов:
 
Для этого рассмотрим отдельно количество сделанных операций каждого из четырёх типов:
* изначально, до обработки группы, рабочий отрезок был <tex>[a \ldots b]</tex>, для обработки первого запроса может потребоваться <tex>2 \cdot N</tex> операций <tex>\mathtt{add}</tex>, <tex>\mathtt{del}</tex>
+
* изначально, до обработки группы, рабочий отрезок был <tex>[a \ldots b]</tex>, для обработки первого запроса может потребоваться <tex>2 \cdot N</tex> операций <tex>\mathtt{add}</tex>, <tex>\mathtt{del}</tex>;
* <tex>\mathtt{delRight}</tex> не произойдёт ни разу, т.к. рабочий отрезок будет только расширяться в сторону правого конца
+
* <tex>\mathtt{delRight}</tex> между отрезками одной группы не произойдёт ни разу, так как рабочий отрезок внутри одной группы будет только расширяться в сторону правого конца;
* <tex>\mathtt{addRight}</tex> произойдёт суммарно не больше чем <tex>N</tex> раз, так как минимальная правая граница {{---}} <tex>1</tex>, а максимальная {{---}} <tex>N</tex>
+
* <tex>\mathtt{addRight}</tex> в этой группе произойдёт суммарно не больше чем <tex>N</tex> раз, так как минимальная правая граница {{---}} <tex>1</tex>, а максимальная {{---}} <tex>N</tex>;
* для оставшихся двух операций рассмотрим два последовательных запроса <tex>[l_i \ldots r_i]</tex>, <tex>[l_j \ldots r_j]</tex>. Нетрудно заметить, что так как отрезки принадлежат одной группе, то <tex>|l_i - l_j| < K</tex>, следовательно, количество операций <tex>\mathtt{addLeft}</tex> или <tex>\mathtt{delLeft}</tex> также не будет превосходить <tex>K</tex>;
+
* для оставшихся двух операций рассмотрим два последовательных запроса <tex>[l_i \ldots r_i]</tex>, <tex>[l_j \ldots r_j]</tex>. Нетрудно заметить, что так как отрезки принадлежат одной группе, то <tex>|l_i - l_j| < K</tex>, следовательно, количество операций <tex>\mathtt{addLeft}</tex> или <tex>\mathtt{delLeft}</tex> не будет превосходить <tex>K</tex>, а суммарно для всей группы {{---}} <tex>Q_i \cdot K</tex>.
  
 
Таким образом, нетрудно видеть, все группы будут обработаны за время <tex>O \left( \dfrac{N^2}{K}  + K \cdot Q \right) </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>
+
При выборе <tex>K = \sqrt{N}</tex> с учётом сортировки по правой границе получается асимптотика времени <tex>O(Q \cdot \log Q + (N + Q) \cdot \sqrt N)</tex>.
  
 
==Реализация==
 
==Реализация==
Строка 89: Строка 92:
 
   '''return''' current.max.second <font color=green>// находим максимальную пару в множестве</font>
 
   '''return''' current.max.second <font color=green>// находим максимальную пару в множестве</font>
  
Итоговая асимптотика решения: <tex>O(Q \cdot \log Q + (N + Q) \cdot \sqrt{N} \cdot \log N)</tex>
+
Итоговая асимптотика решения: <tex>O(Q \cdot \log Q + (N + Q) \cdot \sqrt{N} \cdot \log N)</tex>.
  
 
== См. также ==
 
== См. также ==

Версия 12:57, 11 июля 2021

Алгоритм Мо (англ. 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].

См. также

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