A structure that allows you to add / remove half-intervals from the set and displays the number of non-intersecting intervals?

Question

Programming

Good afternoon.
Please help with the solution of the following problem:
Give a data structure that allows you to support the set A⊆ℝ and add/remove half-intervals to/from it. Initially, the set A is empty. After that, n queries like "+ l r" or "- l r" are received. The first query corresponds to the operation A←A∪[l,r), the second - to the operation A←A∖[l,r). After each of these queries, it is necessary to print the number of half-intervals that A consists of, that is, such a minimum number k that A is represented as k pairwise disjoint intervals. Give an algorithm that receives a number of n and n requests as input and processes all requests in O(nlogn) time.
Tell me at least in which direction to look and what structure should be used.

Answer 1

I must say right away that the description of the task is slightly different from what I understood from the title.
By the title, I thought that this is a structure that stores some set of pairs (l, r) where l, r denote the ends of the interval. And deleting l, r corresponds to deleting a pair.
But it turned out that this is a structure that stores a set that can be represented as pairs (l, r), where each (l, r) is such a half-interval.
The first thing that comes to mind is set, but set will not work because you need to somehow be able to remove several elements at once (l, r) if + lr comes that covers several elements, then they must be removed quickly. Set, on the other hand, makes it possible to remove them only in m log n, where m is the number of elements to be removed, and n is the size of the tree.
So my suggestion: Cartesian tree.
I would suggest a segment tree if min l and max r were within reasonable limits, as it is easier to write in this case.

Answer 2

Linked list with an even number of elements.
The first element is the leftmost opening point. The next one after him is the one that closes this gap.
Adding and removing elements in such a structure is intuitive. Number of segments - the size of the list in half.
Minus - the asymptotics is not the same. To get the right one, you need to wrap this list in a tree, as the adviser suggested above.