题解：P14380 【MX-S9-T3】「LAOI-16」天外来物

· · 题解

首先非常抱歉赛时放过去了 \log^2 n 做法。

其次某些对本题有怨气的选手可以去找出题人 wangziyue_AK。

出题人题解。

以下称一个区间的天外来物为一个区间的集合，一个区间的关键点为其集合中的点。我们定义内部点为连接了至少两个关键点的关键点，其余关键点为外部点。则我们发现外部点一定在区间中，否则该点可以删去，而内部点可以不在区间内。

有结论：两个集合相同的区间一定有交，且交的集合也与它们的集合相同。因为两个区间的集合都一定存在外部点，且其外部点集一定相同，这些外部点又一定同时出现在这两个区间内，所以外部点集一定在其交之中。又因为其交包含了所有的外部点，所以其集合也相同。

那么对于集合为同一种的区间全部取交，得到的区间一定不能再缩短，而其余区间可以通过取交删除右端点或左端点。所以只对删除左右端点都会影响集合的区间即左右端点都是外部点的区间计数就可以做到数出集合的种数。

考虑一个点 i 作为左端点时，满足其是外部点的右端点是一段从 i 开始的区间，记这个区间为 rt_i，同样定义 lt。则答案为 \sum_{l=L}^{R}\sum_{r=l}^{R}[r\le rt_l\wedge l\ge lt_r] 。

先考虑计算 lt 和 rt。对于 rt_l，应该是其第一次成为内部点的 r 减一（没有就视为 n+1）。其第一次成为内部点也即第一次有两个子树中有点出现在了区间内（子树补也视为其子树，即以它为根的子树）。所以对每个子树找出编号大于 l 的点的编号的最小值，其次小值就是第一次成为内部点的时间。所以从大往小扫描 l，以 dfn 序建线段树维护单点修，区间最小值即可。lt 同理。

再来解决计算答案的问题，考虑扫描线。设扫到了 j，对于每个点 i 维护 f_i 表示以其为左端点，且右端点小于等于 j 的合法区间个数。维护 flag_i 为 [rt_i\ge j]，可以在扫描线的同时维护，然后对于 \forall i\in[lt_j,j],f_i\gets f_i+flag_i 即可维护 f，用线段树维护区间 f 的和 以及 flag 的和即可。

总复杂度 O((n+q)\log{n})，空间线性。