17
правок
Изменения
Нет описания правки
Разделим все запросы на блоки размера <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>3 \cdot O(N + Q_i \cdot K)</tex> операций <tex>\mathtt{add}</tex> и <tex>\mathtt{del}</tex> , где <tex>Q_i</tex> {{---}} количество запросов, принадлежащих группе под номером <tex>i</tex>.
==Доказательство==Докажем, что на обработку одной группы суммарно уйдёт не больше чем <tex>3 \cdot N + Q_i \cdot K</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> не произойдёт ни разу, т.к. рабочий отрезок будет только расширяться в сторону правого конца
