Journeys 题解

思路

一条描述把区间 $A=[a,b]$ 与区间 $B=[c,d]$ 完全相连。若展开所有道路，边数可能达到 $O(mn^2)$。需要用线段树节点代表连续区间。

建立两棵共享国家叶子的线段树：上行树的零代价边从儿子指向父亲，使一个国家能够到达所有包含它的规范区间；下行树的零代价边从父亲指向儿子，使一个规范区间能够到达其中所有国家。

对每条双向道路描述建立两个不同的中转点。第一个中转点接收上行树中覆盖 $A$ 的节点，并用代价 $1$ 指向下行树中覆盖 $B$ 的节点；第二个中转点处理 $B$ 到 $A$ 的方向。必须使用两个中转点：若两边共用一个点，就会凭空产生 $A$ 内部或 $B$ 内部的道路。

图中只有权值 $0$ 和 $1$，因此从首都国家节点执行 0-1 BFS。每个国家节点的最短距离就是所求答案。

做法

1. 递归建立上行树和下行树；叶子直接使用对应国家节点。
2. 把每个输入区间分解成 $O(\log n)$ 个线段树规范区间，并按两个方向连接各自的中转点。
3. 用双端队列执行 0-1 BFS：经过零边时压入队首，经过一边时压入队尾。
4. 依次输出国家节点 $1$ 到 $n$ 的距离。

证明

对任意国家 $x\in A$，在上行树中沿零边向上，必定能到达 $A$ 的规范分解中唯一包含 $x$ 的节点；随后到达 $A\to B$ 中转点，再用一条代价为 $1$ 的边进入 $B$ 的某个规范节点，并沿下行树零边到达任意 $y\in B$。因此每条原道路都对应图中总代价恰为 $1$ 的路径。

反过来，从国家节点离开并最终到达另一个国家节点时，唯一会增加代价的边是某个方向中转点到目标区间的边。进入该中转点要求起点国家属于该方向的源区间，离开后只能到达目标区间内的国家，所以每次代价增加都对应一条真实道路。两个方向使用不同中转点，不会生成同侧区间内部的伪道路。

于是压缩图中任意两国之间路径的代价，与原图中经过的道路数一一对应。0-1 BFS 正确求出压缩图最短路，因此输出即为原图最少道路数。

复杂度

线段树图有 $O(n+m)$ 个节点和 $O(n+m\log n)$ 条边。建图与 0-1 BFS 的时间复杂度均为 $O(n+m\log n)$，空间复杂度为 $O(n+m\log n)$。