17
правок
Изменения
Нет описания правки
* <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>Q_i \cdot K</tex>;
Таким образом, нетрудно видеть, все группы будут обработаны за время <tex>O \left( \dfrac{N^2}{K} + K \cdot Q \right) </tex>.
