P6645 [CCO 2020] Interval Collection

This problem statement is from [LOJ](https://loj.ac/p/3321).

Altina is collecting intervals. A pair of positive integers $[l, r]$ with $l < r$ is an interval, and we call the length of such an interval $r - l$. We say that interval $[l, r]$ contains interval $[x, y]$ if and only if $l \le x$ and $y \le r$. In particular, every interval contains itself. For a non-empty set $S$, define its **maximum common sub-interval** as the longest interval that is contained in every interval in $S$. If no such interval exists, it is undefined. For a non-empty set $S$, define its **minimum common super-interval** as the shortest interval that contains every interval in $S$. Note that such an interval always exists. Initially, there are no intervals in Altina’s collection. Then $Q$ events will happen, which change Altina’s collection. 1. Altina adds an interval $[l, r]$ to her collection. If $[l, r]$ already exists in the collection, it should be counted as a different interval. 2. Altina removes an interval $[l, r]$ that already exists in the collection. If there are multiple identical ones, remove exactly one. After each event, Altina chooses a non-empty subset $S$ of her collection, satisfying the following rules: - Among all choices, she will choose one where the maximum common sub-interval is undefined. If no such choice exists, she will choose one where the length of the maximum common sub-interval is as small as possible. - Among all sets $S$ that satisfy the rule above, she will choose one where the length of the minimum common super-interval is as small as possible. After each event, output the length of the minimum common super-interval of the set $S$ that Altina will choose.

The first line contains a positive integer $Q$, the number of events. The next $Q$ lines each describe an event in one of the following formats: - $\mathtt{A}\;l\;r$: add an interval $[l, r]$ to Altina’s collection. - $\mathtt{R}\;l\;r$: remove an interval $[l, r]$ from Altina’s collection. It is guaranteed that this interval exists in her collection, and that after removal her collection is non-empty.

Output $Q$ lines. Each line contains one positive integer, the length of the minimum common super-interval of the set $S$ that Altina will choose after that event.

#### Sample Explanation Add $[1,5]$. Choosing $[1,5]$ is optimal, so the answer is $4$. Add $[2,7]$. Choosing $[1,5],[2,7]$ is optimal, so the answer is $7-1=6$. Add $[4,6]$. Choosing $[1,5],[4,6]$ is optimal, so the answer is $6-1=5$. Add $[6,8]$. Choosing $[4,6],[6,8]$ is optimal, so the answer is $8-4=4$. Remove $[4,6]$. Choosing $[1,5],[6,8]$ is optimal, so the answer is $8-1=7$. #### Subtasks **This problem uses bundled testdata.** - Subtask 1 ($12$ points): $Q\le 500$. - Subtask 2 ($32$ points): $Q\le 1.2\times 10^4$. - Subtask 3 ($28$ points): $Q\le 5\times 10^4$. - Subtask 4 ($16$ points): For any two intervals $(l_1,r_1)$ and $(l_2,r_2)$, it is guaranteed that $r_1