首页 > 笔记 > 李超线段树总结

李超线段树总结

写在前面:

最近很久没有发文章了,但是写了还是很多,大概有10+篇草稿。主要是没大有时间找/做例题。以后打算少放一些例题,以后有时间做了后再放在后面。

正文

用一道例题来引入。

Description

要求在平面直角坐标系下维护两个操作:
1.在平面上加入一条线段。记第i条被插入的线段的标号为i。
2.给定一个数k,询问与直线 x = k相交的线段中,交点最靠上的线段的编号。

Input

第一行一个整数n,表示共n 个操作。

接下来n行,每行第一个数为0或1。

若该数为 0,则后面跟着一个正整数 k,表示询问与直线x = ((k +lastans–1)%39989+1)相交的线段中交点(包括在端点相交的情形)最靠上的线段的编号,其中%表示取余。若某条线段为直线的一部分,则视作直线与线段交于该线段y坐标最大处。若有多条线段符合要求,输出编号最小的线段的编号。

若该数为 1,则后面跟着四个正整数 x0, y0, x1, y1,表示插入一条两个端点为((x0+lastans-1)%39989+1,(y0+lastans-1)%10^9+1)和((x1+lastans-1)%39989+1,(y1+lastans-1)%10^9+1) 的线段。

其中lastans为上一次询问的答案。初始时lastans=0。

Output

对于每个 0操作,输出一行,包含一个正整数,表示交点最靠上的线段的编号。若不存在与直线相交的线段,答案为0。

Sample Input

6
1 8 5 10 8
1 6 7 2 6
0 2
0 9
1 4 7 6 7
0 5

Sample Output

2
0 3

HINT

对于100%的数据,1 ≤ n ≤ 10^5 , 1 ≤ k, x0, x1 ≤ 39989, 1 ≤ y0 ≤ y1 ≤ 10^9。

题意:在坐标轴里插入一堆线段,每次给出k,查询x=k这条直线上最上面的一条直线。

如何用线段树解决这个问题呢?我们先把坐标轴用线段树维护一下,每个节点代表一个区间。每个节点的标记里记下经过这个节点的一次函数(k和b的值)。

这样子插入直线就可以把直线的定义域分成logn个区间,每个区间里记一下直线。每次要查询的时候就先找到最下面的子节点,一路找到根节点,统计下最高的就可以了。

但是插入的时候出现冲突了怎么办?

红色代表区间的大小,橙色是mid,黑色是原直线,蓝色是插入直线。

这样的话我们发现黑色直线在左边的区间就没有任何存在的必要了,因为蓝色直线是完全覆盖掉黑色直线的。这样的话我们就可以在这个节点只保留蓝色的直线,然后开始用右半边的黑色直线来更新下面的区间。

这就是一个李超树的实现过程。标记永久化,直到插入的时候才更新标记。

给个代码

例题

BZOJ3938
BZOJ4515


如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×