维护直线的不同思路

来看这样的查询：

\[ f(x) = \min_{i}\{k_ix + b_i\} \]

李超线段树

这很暴力。直接正向维护直线即可。

转化为截距

如果最终的 \(\arg \min\) 是 \(j\)，那么有：

\[ \begin{aligned} f(x) &= k_jx + b_j \\ b_j &= x\cdot(-k_j) + f(x) \end{aligned} \]

注意查询的时候，其实 \(x\) 也是已知的。我们把 \(x\) 看成斜率，就转换成如下问题：

在点集 \((-k_i, b_i)\) 中，找出一个点 \(j\)，使得过 \(j\) 的斜率为 \(x\) 的直线截距最小。

可以维护点集的凸包，然后二分凸包上的点即可找到 \(j\)。

后面的步骤就非常像 wqs 二分