note-li-chao-tree

cirnovsky · 2021-05-15 16:50:06 · 个人记录

用来维护单点点值最优线段的东西。

有两种写法。

• 维护中点最优

这种写法不太正常，设我们现在维护的区间是 [l,r]，设插入的函数编号是 t，函数 t 在 x 处的点值是 f(x,t)。

设当前最优线段是 x，若线段 t 在 l 和 r 上都较 x 更优，那就直接把区间最优改成 t。

否则取到在 mid 处的点值，看哪边更优往下递归。

• 维护区间最优

区别不大哦，但是各判一下左右端点即可。

例题 1303G，挺不错的。