李超线段树的板子

 

简介

李超线段树主要是维护的这些东西：

1. 在平面上加入一条线段。记第 条被插入的线段的标号为 。
2. 给定一个数 ，询问与直线 相交的线段中，交点纵坐标最大的线段的编号。

主要操作

插入

我们这个线段树，一个 的区间，维护的是 坐标范围为 的线段们的中点纵坐标最大的线段。

现在我们插进去一条 坐标范围为 的一条线段。

记现在的线段编号为 ，之前的线段编号为 （因为是在树中，这个 代表 区间）。

然后如果现在线段的中点纵坐标大于 的中点纵坐标，那么就把 和 交换一下。（是交换，不是替换）！！！

交换就把所有的插入线段的情况，都变为了中点纵坐标较小的线段插入中点纵坐标较大的线段。

如果 的所有部分都在 的下面，那就不用管，因为 在区间 的任何时刻纵坐标都比他大，没有搞头。

但是如果有交点的话，就有搞头了。

于是我们递归到 的那个区间，然后再执行上面的操作。然后就这样一遍遍递归直到叶子节点。

因为两条线段的交点只能有 个，所以递归只会递归一侧，时间复杂度 。

查询

查询因为是只查询单独一个 坐标的 最大的线段的编号，所以我们一直递归直到那个区间。

但是因为我们这个李超线段树是没有 pushdown 操作的，所以我们考虑标记永久化。

这个是怎么做的呢？就是在递归的过程中，递归到的每一个区间都把他的最优线段提出来，然后把他用 来计算 坐标。最终的最大值就是在递归的路程中的所有线段的 的最大值。而编号也就随着这个更新了。是好维护的。

板题：P4097