390
правок
Изменения
→Нахождение всех интервалов, покрывающих данную точку
===Нахождение всех интервалов, покрывающих данную точку===
{{ЗадачаСписок с пропусками используют для решение одной из классических задач |definition = Есть <tex>-q</tex> нахождения количество интервалов, которые покрывают данную точку. Более подробное условие задачи: пусть у нас есть поле, координаты которого <tex>-</tex> любые (возможно вещественные) числа, а также задано два типа запросовдвух видов:
# Добавить интервал <tex>[L, R]</tex>
# Задана точка <tex>x</tex>. Найти На каждый запрос второго типа необходимо вывести количество интервалов, которые покрывают данную точку.Список с пропусками позволяет решать данную задачу онлайн за <tex>O(\log{q})</tex> времени, где <tex>q</tex> <tex>-</tex> количество запросов. В отличии от дерева отрезков, для которого требуется, чтобы координаты были целыми числами в небольшом диапазоне, списку с пропусками не важно, какого типа координаты, главное, чтобы их можно было сравнивать.}
Решение данной задачи заключается в том, что когда приходит запрос добавления интервала, то мы добавляем левую и правую границу (если до этого они не были добавлены). Потом идём от левой точки до правой и на пути прибавляем <tex>1</tex>. Когда нам приходит запрос второго типа, то рекурсивно спускаемся сверху вниз и суммируем все числа, лежащие на пути между двумя ближайшими вершинами, между которыми находится заданная точка. Очевидно, что оба запроса мы обрабатываем за <tex>O(\log{n})</tex>, при этом нет никакой необходимости знать запросы заранее.
