17
правок
Изменения
→Алгоритм
Изначально в качестве рабочего отрезка можно взять любой отрезок. Для удобства чтения будем считать изначальным отрезок <tex>[1;1)</tex>, то есть <tex>a = 1</tex>, <tex>b = 0</tex>, фактически {{---}} пустой отрезок.
Запишем все запросы в массив, некоторым образом их отсортируем и (как конкретно требуется сортировать будет сказано чуть позже) будем их обрабатывать в том порядке, в котором они будут лежать в массиве после [[Сортировки | сортировки]].
Допустим, что текущий рабочий отрезок — <tex>[a \ldots b]</tex>, а первый необработанный запрос — <tex>[l_i, r_i]</tex> тогда сначала расширим наш отрезок,
Разделим все запросы на блоки размера <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>O(N + Q_i \cdot K)</tex>, где <tex>Q_i</tex> {{---}} количество запросов, принадлежащих группе под номером <tex>i</tex>.
==Доказательство==
