P6645 [CCO 2020] Interval Collection

本题题面来自 [LOJ](https://loj.ac/p/3321)。

Altina 正进行区间收藏。一对满足 $l < r$ 的正整数 $[l, r]$ 为一个区间，我们称这样的区间的长度为 $r - l$。 我们称区间 $[l, r]$ 包含区间 $[x, y]$，当且仅当 $l \le x$ 并且 $y \le r$。特别地，每个区间都包含自身。 定义一个非空集合 $S$ 的**最大公共子区间**为被 $S$ 中每个区间都包含的区间中最长的那个，如果没有这样的区间则未定义。 定义一个非空集合 $S$ 的**最小公共超区间**为包含 $S$ 中每个区间的区间中最短的那个，注意这样的区间总是存在。 初始时，Altina 的收藏中没有任何区间。接下来会发生 $Q$ 个事件，对 Altina 的收藏产生改变。 1. Altina 往她的收藏中添加一个区间 $[l, r]$，如果此时收藏中已有 $[l, r]$，应该被算作不同的两个区间。 2. Altina 移除一个在收藏中已经存在的区间 $[l, r]$，如有多个只以移除恰好一个。 在每个事件发生后，Altina 选择一个她的收藏中的非空子集 $S$，并且满足如下条件： - 在所有的选取方案中，她会选择最大公共子区间未定义的。如果不存在这样的方案，则她会选择最大公共子区间的长度最小的。 - 在所有的满足上述条件的集合 $S$ 中，她会选择最小公共超区间的长度最小的。 请你在每一个事件发生后，输出 Altina 会选择的集合 $S$ 的最小公共超区间的长度。

第一行一个正整数 $Q$，表示将会发生的事件的个数。 接下来 $Q$ 行，每行描述一个事件，格式如下： - $\mathtt{A}\;l\;r$：添加一个区间 $[l, r]$ 到 Altina 的收藏中。 - $\mathtt{R}\;l\;r$：从 Altina 的收藏中移除一个区间 $[l, r]$，保证这个区间在她的收藏中存在，且移除后她的收藏非空。

输出 $Q$ 行，每行一个正整数表示每个事件发生后 Altina 会选择的集合 $S$ 的最小公共超区间的长度。

#### 样例解释 加入 $[1,5]$，选择 $[1,5]$ 最优，答案为 $4$。 加入 $[2,7]$，选择 $[1,5],[2,7]$ 最优，答案为 $7-1=6$。 加入 $[4,6]$，选择 $[1,5],[4,6]$ 最优，答案为 $6-1=5$。 加入 $[6,8]$，选择 $[4,6],[6,8]$ 最优，答案为 $8-4=4$。 删除 $[4,6]$，选择 $[1,5],[6,8]$ 最优，答案为 $8-1=7$。 #### 子任务 **本题使用捆绑测试** - Subtask 1（$12$ 分）：$Q\le 500$。 - Subtask 2（$32$ 分）：$Q\le 1.2\times 10^4$。 - Subtask 3（$28$ 分）：$Q\le 5\times 10^4$。 - Subtask 4（$16$ 分）：对于任两个区间 $(l_1,r_1)$ 和 $(l_2,r_2)$，保证 $r_1