李超线段树
stripe_python · · 算法·理论
P4097 【模板】李超线段树 / [HEOI2013] Segment。
维护平面坐标系,支持
q 次操作:
- 给定
k,b,l,r ,插入线段f(x)=kx+b,x \in [l,r] 。- 给定
x_0 ,求x_0 \in [l_i,r_i] 的f_i(x_0) 取到\max 的i 。强制在线。
插入线段,查询单点最值可以使用李超线段树维护。
对
对于修改,我们将插入线段
-
若
[l_0,r_0] \cap [l,r] =\varnothing ,拒绝这条线段,终止递归。 -
若
[l_0,r_0] \nsubseteq [l,r] ,递归左右儿子即可。 -
若
[l_0,r_i] \subseteq[l,r] ,画图进行分讨:Case 1 插入线段在
[l,r] 内始终不优,终止递归。Case 2 插入线段在
[l,r] 内始终不劣,更新最优线段后终止递归。Case 3 插入线段与最优线段在
[l,r] 内有交点。根据m 处取值更新最优线段。若交点在[l,m] 则递归左子树,在(m,r] 则递归右子树。
修改时李超树始终保持单侧递归,复杂度
李超树可以视作一种特殊的单侧递归线段树,最优线段是标记永久化的体现。
最优线段构成线段集合的包络线,对偶后维护的就是点集的凸包。因此李超树的本质是动态凸包。
P10980 任务安排 4.1
李超树维护斜率优化 DP。
设
其中
不妨令
问题可以视作,插入直线