【题解】【Nikkei 2019 Final F】 Flights

· · 题解

考虑持久化线段树优化建图。假设你已经掌握了线段树优化建图的方法。

首先将点按照 x 为第一关键字，y 为第二关键字排序。

考虑持久化线段树。插入一个节点的时候，至多会有一个节点被顶替掉。注意到，如果 X_k\le X_j，那么能走到点 j 的点一定能走到点 k，反之不然。所以在图上体现为新版本的叶子与旧版本的叶子之间的连边。

那么我们略微修改一下图的构造。我们还是一样地建出一棵出树一棵入树，不一样的是，本题中，我们将点 i 连向出树中对应的叶子节点，将入树中对应的叶子节点连向点 i。更新版本时，新版本的叶子向旧版本的叶子连边，具体地就是入树中新版本连旧版本，出树中旧版本连新版本。

然后就将点 i 与 \log V 个区间连边即可。需要轻微卡常，代码。

时间复杂度就是 \Theta(n\log ^2 n) 的。

/bx skz。