KTT 学习笔记

amaimaic · 2025-03-02 00:34:20 · 个人记录

在做 4118 弱化版的时候发现了这样的小清新线段树，学习了一个下午后终于看懂了，发誓要写一篇小白也看得懂的学习笔记。

考虑这样的一个问题：

你需要维护 n 个一次函数 f(x) = kx + b。

询问给定一个单调增的 v 与区间 l, r。

问你区间内函数对于 x = v 时的取值最值。

观察一些性质：

• 一次函数之间的交点只有一个（暂时不考虑重合）
• 每个一次函数对于一个区间，能够取到最值的 x 一定是一个区间。

第二个有点拗口，但是看这样一张图，你会发现 每一个一次函数都只有一段在最上面。

而且段数显然是 n 级别的。

我们考虑用线段树维护当前区间的 最值线段 以及 下一次发生变动的 x。

前者是好维护的，后者直接对左右儿子取 \min 即可。

EI 已经证明了复杂度是 q\log ^ 3 的，你要问我我也不会证，挂个论文链接吧 XD。