李超线段树

引入

洛谷 4097 [HEOI2013]Segment

要求在平面直角坐标系下维护两个操作（强制在线）：

1. 在平面上加入一条线段。记第 $i$ 条被插入的线段的标号为 $i$，该线段的两个端点分别为 $(x_0,y_0)$，$(x_1,y_1)$。
2. 给定一个数 $k$，询问与直线 $x=k$ 相交的线段中，交点纵坐标最大的线段的编号（若有多条线段与查询直线的交点纵坐标都是最大的，则输出编号最小的线段）。特别地，若不存在线段与给定直线相交，输出 $0$。

数据满足：操作总数 $1\le n\le {10}^5$，$1\le k,x_0,x_1\le 39989$，$1\le y_0,y_1\le {10}^9$。

我们发现，传统的线段树无法很好地维护这样的信息。这种情况下，李超线段树 便应运而生。

过程

我们可以把任务转化为维护如下操作：

• 加入一个一次函数，定义域为 $[l,r]$；
• 给定 $k$，求定义域包含 $k$ 的所有一次函数中，在 $x=k$ 处取值最大的那个，如果有多个函数取值相同，选编号最小的。

注意

当线段垂直于 $x$ 轴时，会出现除以零的情况。假设线段两端点分别为 $(x,y_0)$ 和 $(x,y_1)$，$y_0

---

本页面最近更新：2025/8/30 13:34:30，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：StudyingFather, Tiphereth-A, do-while-true, iamtwz, aofall, ChungZH, codewasp942, CoelacanthusHex, Enter-tainer, henrytbtrue, HeRaNO, Ir1d, Jelefy, kenlig, ksyx, leoleoasd, Marcythm, mcendu, Persdre, shuzhouliu, usada-pekora-286
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用