@newproger2017

Структура, позволяющая добавлять/удалять полуинтервалы из множества и выводящая количество непересекающихся интервалов?

Добрый день.

Помогите пожалуйста с решением следующей задачи:

Приведите структуру данных, позволяющих поддерживать множество A⊆ℝ и добавлять/удалять полуинтервалы в/из него. Изначально множество A пусто. После этого поступает n запросов типа "+ l r" или "- l r". Первый запрос соответсвует операции A←A∪[l,r), второй — операции A←A∖[l,r). После каждого из таких запросов необходимо вывести количество полуинтервалов, из которого состоит A, то есть такое минимальное число k, что A представляется в виде k попарно непересекающихся интервалов. Приведите алгоритм, получающий на вход число n и n запросов который за время O(nlogn) обрабатывает все запросы.

Подскажите хотя бы в какую сторону смотреть и какая структура должна быть использована.
  • Вопрос задан
  • 358 просмотров
Пригласить эксперта
Ответы на вопрос 2
@tomatho
Сразу скажу, что описание задачи чуть-чуть отличается от того, что я понял по заголовку.
По заголовку я подумал, что это структура хранящая некоторое множество из пар (l, r) где l, r обозначают концы интервала. И удаление l, r соответствует удалению пары.
А оказалось, что это структура которая хранит множество, которое представимо в виде пар (l, r), где каждое (l, r) - такой полуинтервал.

Первое, что лезет в голову - set, но set не подойдёт так как надо как-то уметь удалять сразу несколько элементов (l, r) если пришел + l r который покрывает несколько элементов, то их надо удалять быстро. Set же даёт возможность их удалять только за m log n где m - количество элементов которые надо удалить, и n размер дерева.

Так что моё предложение: декартово дерево.
Я бы предложил дерево отрезков, если бы min l и max r были в разумных пределах, так как оно проще пишется в этом случае.
Ответ написан
Labunsky
@Labunsky
Я есть на хабре
Связный список с четным количеством элементов.
Первый элемент - самая левая открывающая точка. Следующий за ним - закрывающая этот промежуток.
Добавление и удаление элементов в такой структуре интуитивно. Количество отрезков - размер списка пополам.
Минус - асимптотика не та. Чтобы получить нужную, надо этот список завернуть в дерево, как предлагал советчик выше.
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы