Структура, позволяющая добавлять/удалять полуинтервалы из множества и выводящая количество непересекающихся интервалов?
Сразу скажу, что описание задачи чуть-чуть отличается от того, что я понял по заголовку.
По заголовку я подумал, что это структура хранящая некоторое множество из пар (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 были в разумных пределах,  так как оно проще пишется в этом случае.
Связный список с четным количеством элементов. 
Первый элемент - самая левая открывающая точка. Следующий за ним - закрывающая этот промежуток.
Добавление и удаление элементов в такой структуре интуитивно. Количество отрезков - размер списка пополам.
Минус - асимптотика не та. Чтобы получить нужную, надо этот список завернуть в дерево, как предлагал советчик выше.