17
правок
Изменения
Нет описания правки
Для этого рассмотрим отдельно количество сделанных операций каждого из четырёх типов:
* изначально, до обработки группы, рабочий отрезок был <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>.
