P2161 [SHOI2009] Venue Reservation

Formal statement: You need to maintain a set $S$ of segments on the number line, supporting two operations: `A l r` means to delete from $S$ all segments that intersect the segment $[l, r]$, and then insert $[l, r]$ into $S$. `B` queries the number of elements in $S$. For operation `A`, you also need to output the number of elements deleted each time.

There is an empty auditorium in the PP Building that can provide a meeting venue for companies or organizations. Most of these meetings require several consecutive days (some may require only one day). However, there is only one venue, so the times of different meetings cannot conflict. That is, the end date of the previous meeting must be before the start date of the next meeting. Therefore, to accept a new reservation request, all reservations that conflict with it must be rejected. In general, if the PP Building has already accepted a venue reservation (for example, from day $10$ to day $15$), then it will not accept any reservation that conflicts with it (for example, from day $12$ to day $17$). However, sometimes for economic reasons, the PP Building will reject one or even several previously accepted reservations in order to accept a new one. Therefore, the administrator QQ’s notebook often records such information. (For convenience in this problem, all dates are represented by an integer.) For example, if a $10$-day meeting runs from day $90$ to day $99$, then the earliest the next meeting can start is day $100$. (There is a contradiction here; if you cannot understand, please refer to the formal description.) Recently, the workload has been increasing. The administrator QQ hopes you, a participant in SHTSC, can design a computer system to make the work easier. This system should be able to perform the following two operations: Operation `A`: A new reservation is from day $start$ to day $end$, and all reservations that conflict with it are rejected. When performing this operation, your system should return the number of reservations that were rejected for this new reservation, so QQ can check against the records. Operation `B`: Your system should return the current total number of valid reservations.

The first line contains a positive integer $n$, the number of operations. Then follow $n$ lines, each describing one operation, which is one of the two types above.

Output $n$ lines, each with one integer, representing the answer for the corresponding operation.

Constraints: For $100\%$ of the testdata, $1 \le n \le 2 \times 10^5$, $1 \le l \le r \le 10^5$. Translated by ChatGPT 5