CF269D Maximum Waterfall

发表于 更新于 分类于 ， ， 阅读次数：

题意：给出若干条水平线段，形如 。

此外，还有两条无限延伸的线段，一条在 ，另一条在 。

若两条线段 满足如下条件，则在图中连接有向边 。

  • ，即两者的投影有交。

  • 不存在 使得有序二元组 与 满足上述条件。

边权为 。

问从 到 的最小瓶颈路，即最小边权最大的路径。输出这个最小边权。

保证各个线段没有交点。

，时限 。

5min 胡出来，太感动了……

首先不难发现该图是个 DAG，于是在 DAG 上进行 DP 求最小瓶颈路，复杂度即为 。

考虑数据结构优化。

将所有线段按照 从低到高排序，逐个进行转移。（这捕捉了该 DAG 的一种拓扑序）

对于每个线段，其可能的转移前驱为：下方所有线段的上包络线中，在自己投影中的部分。

如图，蓝色描边为可能转移的线段：

不难发现，此后这些蓝色部分就被新加入的线段覆盖了。维护上包络线等价于 ODT，所以有结论：每次转移涉及到的候选线段的条数和是 的。

在按顺序取出各个候选线段后，再用条件 ③ 除去不合法的线段。

利用上包络线的性质不难证明，每个候选线段只需要检查左右两个线段是否会导致自己不合法。

转移时暴力即可。

ODT 可以使用线段树或平衡树实现。

复杂度 。