斜率优化 \(\in\) 决策单调性，但是斜优其实可拓展性较差、甚至整个思路都挺莫名其妙，所以我来重构决策单调性体系了。
注意到“我”又回来了。因为是学习笔记不得不记录思考过程，也就不得不把“我”引进来。
我们要探讨一类问题的优化策略：
给定 \(w{i,j}\)，对 \(i \in [1,n]\) 求 \(f_{i} = \min_{j=1}^{i-1} \{w_{j,i} + f_j\}\)。
没有数据范围，我们要研究对什么特征的 \(w\) 能有怎么样的优化。
记 \(f_i\) 的决策点为 \(p_i\)，若 \(p_i\) 单调不减，则 \(f_i\) 有决策单调性。
把 \(f_j + w_{j,i}\) 看成关于 \(i\) 的函数，那么每次我们要加入一个函数、查询某点处函数极值。
如果能保证任意两个函数最多相交一次，可以直接维护最优凸壳（事实上这时连接两个点的不一定是直线但一定是某个函数的一段），维护连续两个点横坐标与连接它们的函数的标号。这个似乎被叫做二分栈，斜率优化可以完全被它取代。
如果能保证 \(i \to \infty\) 时新插入函数最优，则可以直接在最右边插入新函数，不断弹出不够优的函数（一定是一段后缀）。查询点递增可以直接挪左端点，否则可以二分之。复杂度均摊是 \(O(n \cdot \omega(n))\) 或 \(O(n \log n \cdot \omega(n))\)（询问点无序），\(\omega(n)\) 是找到两函数交点的时间复杂度。容易发现插入直线时是漂亮的 \(O(n)\)，与斜率优化的复杂度一致，而且非常自然、可拓展化，不局限于直线。
P5504 插入的是二次函数，复杂度多一只 \(\log\)（二分交点）。
CF1067D 插入的是直线但求的点值要到 \(10^{18}\) 的范围，所以要二分交点
P3515 插入的是二分之一次函数，
以上建立在函数容易求交点或单点求值的基础上，如果无法轻易单点求值，就需要另辟蹊径。
标签：二分,函数,复杂度,决策,笔记,插入,单调 From： https://www.cnblogs.com/purplevine/p/16990286.html