跳转至

李超线段树

引入

洛谷 4097 [HEOI2013]Segment

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

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

数据满足：操作总数 \(1 \leq n \leq 10^5\)，\(1 \leq k, x_0, x_1 \leq 39989\)，\(1 \leq y_0, y_1 \leq 10^9\)。

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

过程

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

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

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

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用