斜率优化抽象做法

作为李超线段树的忠实用户，斜率优化是一定首选李超线段树的。

但是，有时候会碰到这样的情况：

• 时间复杂度为 \(\mathcal{O}(nk)\)，其中 \(n\leq 10^5, k\leq 200\)。
• 时间复杂度为 \(\mathcal{O}(n\log_2 V)\)，卡双 \(\log\)。

这个时候我们不得不舍弃李超线段树的一个 \(\log\)，转而投靠单调队列的线性复杂度。

但是作为蒟蒻的我，完全想不懂 \(b = y-kx\) 然后求最小截距的 nb 维护方法。在近日学习到决策单调性的二分队列做法后，想出如下做法，当然这个做法各位读者可能都想到过：

• 在二分队列的过程中，我们本质上要求出 \([l,r]\) 中变更决策点的位置 \(p\)，但是斜率优化的代价式是一条直线，位置 \(p\) 可以用数学方法求出，于是就省去了 \(\log\)。

相当于我们在队列中维护 \((l,r,f(x))\) 三元组，\(f(x)\) 为一直线，表示当 \(x\in [l,r]\) 时依靠 \(f(x)\) 计算答案。更新与二分队列的决策单调性 DP 完全一致。

在 \(\mathcal{O}(n)\) 一次的斜率优化中保证的性质，也保证可以使用这样的做法。

当然如果不卡 \(\log\) 的话，那就直接转战李超线段树吧。