首先设 $d_u$ 表示到 $0$ 的距离，$d_S\leq d_T$。

我们加入首尾层之间的边之后，对于剩下的边我们要检查所有的权值 $d$ 区间 $[l,r]$，判断他们之间的边连接之后是否连通。

首先，很显然的，我们先往两边分别扫描线，建出两边的 MST。以左边为例，MST 中的一条边表示左端点 $\leq x$ 时两端会连通，设其权值 $y=d_S-x$。右边同理。

我们给出结论：$\sum y=O(n)$。原因是我们尝试构造一张图满足我们求出的 MST：很明显我们先合并 $y$ 的边，如果设每个连通块的势能 $p_a$ 为其中最大的 $y$，那么一次合并消耗的势能为 $2y-p_a-p_b$。我们发现最终的势能比最初的势能高 $O(n)$，而总势能增加量为 $2y$，势能减少量与其同阶，所以 $\sum y=O(n)$。

所以我们给出如下做法：求出集合 $L,R$ 分别表示两边的 $y$ 组成的不可重集。每次去除 $L,R$ 最小值中较小的那个，并用它更新另一个集合中的所有数（也就是从小到大加入所有边直到连通，然后回溯）。这样很明显所有对 $[l,r]$ 都会被更新至少一次。

我们设值为 $y$ 的边数为 $f_y$，那么其中每条边最多会被更新 $y$ 次，所以总更新次数为 $\sum f_y\times y=O(n)$。总复杂度为 $O(n\log n)$。其中的 $\log$ 为并查集复杂度。