李超线段树,本质上是一个线段树变种,旨在解决在一个区间内,多条直线(计算机应用大多数都是线段)与直线$x=?$的最高交点(或者是最低交点,道理是一样的),之后通过上传成为区间的最大值(最小值)。

操作大概就是标记永久化线段树。

对于一个区间$[l,r]$,要解决的问题也就是区间$[l,r]$中的最大值(都以最大值为例了)。

关于一次函数,无疑它是单调的,也就是最大值要么出现在$l$要么在$r$,因此询问时亦可以根据这个减少计算量。

插入线段是最为关键的操作。

对于一个区间$[l,r]$,若已经存在线段标记$id$,考虑$id$与直线$m$的优劣性,

比较明显的两种情况就是:

$id$线段在$[l,r]$整体都在$m$之上,那么直线$m$对于区间$[l,r]$下属的所有子区间一定不是最优线段。

同理,若都在$m$之下,则需要剔除$id$这条无用线段。

考虑两条线段均有可能产生贡献,也就是有可能为区间$[l,r]$下属子区间的最优线段。

仔细想想,不难发现其实就是两条线段有交点的情况,

本着线段树区间由大到小的人道思想(其实是正确性的考虑),若交点小于$mid=(l+r)/2$,再结合斜率进行考虑,在这里斜率$k_m>k_{id}$,则$id$仅有可能对左区间产生贡献,因此需要更改当前区间的标记,并下传$id$到左区间。

同理地,可以推出其他三种情况。

例题 「SDOI2016」游戏

题解可以在我的博客里搜寻。