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

Question

[newproger2017]

Добрый день.

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

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

Подскажите хотя бы в какую сторону смотреть и какая структура должна быть использована.

Comments

[tuwkan]

В лекции, которые предшествовали экзамену вероятно. В последний модуль как я помню.

Answer 1

[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 были в разумных пределах, так как оно проще пишется в этом случае.

Comments

[tuwkan]

А там код и не надо писать, тока привести такую структуру. Это экзамен с code.stepic. И да, последний модуль там как раз про деревья

[tsarevfs]

Сет вроде подойдет. Да, удаление (и добавление) может занимать m log n, но поскольку нельзя удалять больше чем создали, сумма всех m < n. Это так, потому что одна операция не может добавить больше 1 отрезка.

[tomatho]

tsarevfs: должен согласиться.

Answer 2

[Labunsky]

Связный список с четным количеством элементов.
Первый элемент - самая левая открывающая точка. Следующий за ним - закрывающая этот промежуток.
Добавление и удаление элементов в такой структуре интуитивно. Количество отрезков - размер списка пополам.
Минус - асимптотика не та. Чтобы получить нужную, надо этот список завернуть в дерево, как предлагал советчик выше.