Редактирование: Алгоритм Мо

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 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> a > l_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>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> и запомним ответ для этого запроса.
 
  
 
Теперь разберём поподробнее, как именно следует сортировать запросы для достижения вышеназванной асимптотики по времени.
 
Теперь разберём поподробнее, как именно следует сортировать запросы для достижения вышеназванной асимптотики по времени.
Строка 31: Строка 28:
  
 
Для этого рассмотрим отдельно количество сделанных операций каждого из четырёх типов:
 
Для этого рассмотрим отдельно количество сделанных операций каждого из четырёх типов:
* изначально, до обработки группы, рабочий отрезок был <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>Q_i \cdot 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>
  
 
==Реализация==
 
==Реализация==
Строка 92: Строка 89:
 
   '''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>
  
 
== См. также ==
 
== См. также ==

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблон, используемый на этой странице: