以前做斜率不单调的斜率DP(或者说凸包优化),因为不知道CDQ分治怎么弄,然后就学了一下 Splay 的做法……
思想挺简单,但是写起来就…… :< 写完Splay过后又尝试用非旋Treap写,结果一直Wa几天都没调出来 QwQ
幸亏还有李超线段树~
# 斜率不单调的凸包优化
至于什么是凸包优化,也可以看看我写的博客 学习笔记 - 告别精度:从斜率优化到凸包优化(写得比较烂,reader们大概看一下了解意思就可以了)
凸包优化有几种层次:
插入线段的斜率单调,且询问点单调(也就是说插入线段斜率单减或单增,询问点只向一个方向移动):这样的话就可以用单调栈/队列 维护凸包(需要看单调性以及维护的是什么凸包),并且由于询问点单调,那么栈顶/队头就是最优转移点。
这样是线性 $O(n)$ 的。
插入线段的斜率单调,询问点不单调:只能保证最优转移点在维护的凸包上,但是不一定是队头/栈顶是最优的;于是需要在凸包上二分 找最优值。
多了一个二分的复杂度 $O(n\log n)$。
插入线段的斜率不单调(询问点随便单不单调):插入的线段可能会插入到凸包的中间,所以单调栈/队列就不行了,此时可以用平衡树Splay 来插入并且查询。
——但是,还有一个更好用的东西叫做李超线段树 !
# 什么是李超线段树
先以一个问题引入:
在平面上有两种操作(强制在线):
- 插入一条表达式为 $l: y=kx+b$ 的直线,给出 $k,b$。
- 给出 $t$,求当前所有直线中与直线 $x=t$ 交点的纵坐标最大是多少($t\in[1,3\times10^5]$)。
有斜率优化/凸包优化基础的OIer们应该知道,直线取 max 应该是得到一个下凸包,像这样(黑色的):
强制在线嘛……
李超线段树是什么?线段树,当然是要维护区间 $[l,r]$ 的一个信息,李超线段树维护的就是中点处最高的直线。
比如下图,区间 $[0,4]$ 的中点 $x=2$ 的最高直线为红色直线。
利用这一信息,可以在 $O(\log n)$ 的复杂度内插入直线、查询与 $x=t$ 相交的最高点。(这里的 $n$ 指的是查询的 $t$ 的值域范围)
# 实现李超线段树
- 插入直线
李超线段树有一个非常重要的思想:标记永久化。
于是我们可以这样实现李超线段树,假如要把直线 $l_1$ 插入某一区间:
如果当前区间还没有直线标记(不代表没有直线覆盖,因为标记永久化),那么就把标记记为 $l_1$;
如果 $l_1$ 完全覆盖原有线段,像这样(蓝色是 $l_1$,红色是原有线段):
那么 $x=t\in[left,right]$ 与 $l_1$ 的交点一定高于原线段,于是把原有线段直接替换为 $l_1$;
如果 $l_1$ 被原有线段完全覆盖(就是2.反过来),那么 $l_1$ 一定没有原有线段优;这样的话就舍弃 $l_1$ 不做任何更新。
如果 $l_1$ 和原有线段在 $[left,right]$ 中有交点,像这样:
这种情况就无法确定 $x=t\in[left,right]$ 与哪条直线交点更高。根据李超线段树维护的信息,我们需要在两条直线中取与 $x=mid$ 交点更高的一条直线作为标记(也就是上图的黄色直线,剩下的那条就是绿色直线)。
再判断交点:如果在左区间,那么绿色直线在左区间可能比黄色直线高,然后就尝试把绿色直线往左区间插入;右区间类似。
- 查询
由于是标记永久化,查询就比较类似于标记永久化的线段树。比如查询 $x=pos$ 的最高交点,那么就要从线段树一层层递归,直到递归到 $[pos,pos]$ 这个区间——把每个区间的最优线段的交点取 max。
比如这样:
(下面的黄、绿、蓝、橙色线段表现了递归区间的过程)
可以看到橙色区间是没有对应的直线的……
# 源代码
- 插入直线
实际上并不会真的计算交点……精度差别太大了,可以参考下面的代码:
1 | //Calc(l,x) 是计算 l 这条直线在 x 位置的纵坐标 |
- 查询
就非常直白了……
1 | //强行设置 Calc(0,x) 为 -INF (awa) |
# 后续
为了使李超线段树更棒 (<-_<-),就需要很多优化:
- 离散化:就可以缩小线段树维护的区间范围了;而且很好理解它的正确性;
- 动态开点:懒人必备,只是指针的占用的空间略大;
- 可持久化:李超线段树“不可减”,但是加上可持久化就可以撤回了~
嗨呀,忘了还有什么了……就这样吧
The End
Thanks for reading!
咕咕咕……