李超线段树

李超线段树用于维护平面上的直线，支持两种操作：

插入一条线段或直线；
给定 \(k\)，查询与直线 \(x=k\) 相交的所有线段/直线中，交点的 \(y\) 坐标最大/最小的一个。

在李超线段树中，我们在每个节点处至多只会记录一条直线。它代表父亲传下来的直线中，在区间中点处取值最小的一条直线。

考虑如何实现插入。若当前节点 \(p\) 已经有一条直线了，那么：

先比较两条直线在中点处的取值大小，若传下来的更优，则交换二者；
若传入的直线在左端点处取值更优，则向左区间递归传入；
若传入的直线在右端点处取值更优，则向右区间递归传入；

注意到在第一步之后，传入的直线不可能在两端点同时比原直线更优，因此后两步至多有一步会进行，保证了递归是单侧的，因此单次插入的复杂度为 \(O(\log V)\)。

上面的步骤都没有考虑一次函数的定义域。对于线段，我们先把它拍到线段树上，分解成 \(O(\log V)\) 个区间，然后在每个区间分别下传即可。因此对于插入直线，时间复杂度为 \(O(\log V)\)；对于插入线段，时间复杂度为 \(O(\log^2 V)\)。

P4097 【模板】李超线段树

250717 模拟赛 T4

题解见标题链接。

P4069 [SDOI2016] 游戏

树剖套李超线段树，时间复杂度 \(O(n\log^3 n)\)。

CF932F Escape Through Leaf

这道题需要实现李超线段树的合并，就是在线段树合并的过程中如果遇到两侧都有的节点，则将一个节点的直线插入另一个节点的子树中。这里我们说明：李超线段树合并的时间复杂度是 \(O(n\log V)\) 的，其中 \(n\) 表示插入的直线数量，\(V\) 表示值域。这是因为一条直线最多被下传 \(\log V\) 次，其余的复杂度和普通线段树合并一致。