17
правок
Изменения
Нет описания правки
==Алгоритм==
В каждый момент времени поддерживаем структуру данных, в которой хранится будем хранить непрерывный отрезок <tex>[a \ldots b]</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{answer}</tex> {{---}} операция, которая позволяет получить ответ на запрос, если бы его границами был рабочий отрезок.;
Изначально в качестве рабочего отрезка можно взять любой отрезок. Для удобства чтения будем считать изначальным отрезок <tex>[1;1)</tex>, то есть <tex>a = 1</tex>, <tex>b = 0</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{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>O \left( \dfrac{N^2}{K} + K \cdot Q \right) </tex>.
delRight(b)
b -= 1
result[q[i].id] = answer() <font color=green>// получаем ответ на [a;...b] </font>
Рассмотрим для наглядности решение задачи нахождения моды на отрезке:
