Изменения

* <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>[a \ldots b]</tex>, а первый необработанный запрос — <tex>[l_i, r_i]</tex> тогда сначала расширим наш рассмотрим случаи: * Если изначально было <tex> a > l_i </tex>, то будем добавлять в рабочий отрезокэлементы слева по одному, пока граница не совпадёт;используя только операции * Если же это не так, то есть <tex>\mathtt{addLeft}a < l_i </tex>это значит, что в рабочем отрезке присутствуют те элементы, которых там быть не должно, и они должны быть удалены;* При равенстве <tex>a=l_i</tex> никаких действий с левой границей рабочего отрезка производить не потребуется. Аналогично поступим с <tex>b</tex> и <tex>\mathtt{addRight}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> и запомним ответ для этого запроса.

* изначально, до обработки группы, рабочий отрезок был <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>Q_i \cdot K</tex>;.

При выборе <tex>K = \sqrt{N}</tex> с учётом сортировки по правой границе получается асимптотика времени <tex>O(Q \cdot \log Q + (N + Q) \cdot \sqrt N)</tex>.

Итоговая асимптотика решения: <tex>O(Q \cdot \log Q + (N + Q) \cdot \sqrt{N} \cdot \log N)</tex>.