李超线段树

引入

在算法竞赛中,经常有一类这样的问题:

  • 插入一个线段$[(x_1, y_1), (x_2, y_2)]$
  • 询问所有线段中$x_0$所对应的$y_0$的最大值,没有输出$-1$
  • 都是整数 且 值域 $< 1e5$
  • $N <= 1e5$

所谓「李超线段树」,如「吉司机线段树」一样,是一种线段树使用技巧。

算法

考虑线段都没有交点

算法一
Brute-Force-1
对于当前询问枚举每条线段,判断是否经过这个点,更新答案,复杂度$O(N^2)$
算法二
Brute-Force-2
使用数组直接覆盖就行了,复杂度$O(N ^2)$
算法三
使用数据结构维护区间覆盖和查询最大值,复杂度$O(N \cdot logN)$


考虑所插入在查询之前

算法四
直接离线+扫描线处理,维护当前点的最大值,复杂度$O(NlogN)$


考虑所有线段的左右端点值大于询问, 就是把线端看成直线

算法五
Brute-Force-3
每次插入暴力计算交点维护凸壳,插入复杂度$O(N)$
查询复杂度$O(logN)$,总复杂第$O(N^2)$,仍然复杂度爆炸

算法六
动态半平面交?
用一个平衡树(或者std::map)维护凸壳,另一个平衡树std::map维护凸壳上的边,按照极角排序,插入复杂度:均摊$O(logN)$, 查询$O(logN)$,总复杂度$O(NlogN)$


考虑正解

算法七
正解-李超线段树,也只不过是上面算法三和算法四的「加强版」
线段树上只维护最优的线段
对于线段树的每一个节点,维护一个最优的线段
如图,插入黄色的线段,对于这个区间的右半边,蓝色的线段已经没有意义,直接舍弃蓝色更新最优线段为黄色,而对于左边则递归处理。
这样做复杂度线显然是$O(logN)$的。
对于查询操作,每次直接查询到单点,因为没有标记下传,所以在计算的过程中取一个最大值即为答案。
复杂度$O(NlogN)$,可以$\mathbf{AC}$。

模板题

题1:「2017湖南集训Day2T3 – 线段游戏」
题意:插入线段,询问$x0$对应的最高的点,不强制在线。
题解:模板题,可以离散化然后查询。但是因为查询区间只有$[1, 1e5]$,所以不需要离散化也是可以的。
题2: 「BZOJ3165」
题意:题意同上,强制在线
题解:同上,注意几个坑点:
1.对$1e9$取$mod$,而不是对$10$取$mod$异或$9$
2.对于相同的答案输出编号小的(不看题的下场:调到死)
题3: 「BZOJ 1568」
题意:题面描述变得委婉了一点,本质仍然相同,注意小于$0$则输出$0$
题解:套用模板即可安心食用

代码

代码基本都是一样的,放一个「BZOJ3165」的代码

Leave a Reply

Your email address will not be published. Required fields are marked *