前言
这种优化我以前“听”过了很多次，但是好像都没学会qwq。
四边形不等式：
对于二元组 \(w_{x,y}\)，如果在定义域上任取四个点 \(a \le b \le c \le d\)，满足：
\[w_{a,b}+w_{c,d} \ge w_{a,c}+w_{b,d} \]则称 \(w_{x,y}\) 满足四边形不等式。
你会想这鬼东西怎么记？反正我也不想记。
所以也有一个 等价转换：
对于对于二元组 \(w_{x,y}\)，如果在定义域上任取四个点 \(i,j\)，满足：
\[w_{i,j} + w_{i+1,j+1} \le w_{i+1,j}+w_{i,j+1} \]则称 \(w_{x,y}\) 满足四边形不等式。
这东西好记多了，至于怎么证的，我也懒得说qwq。
决策单调性
假设我有一种 dp：
\[f_i = \min_{j=1}^{i} f_{j-1} + w_{j,i}\\ \]这个显然是 \(O(n^2)\)，考虑怎么优化。
有一个很高妙的性质就是：若 \(w_{x,y}\) 满足四边形不等式，则 \(f_i\) 满足决策单调性。
具体的，令 \(g_i\) 表示 \(f_i\) 的最优决策，则 \(g_i\) 单调不降。
有了这个性质就很好优化到 \(O(nlogn)\)，但是怎么写也是一大研究。
二分栈——决策单调性：
二分栈顾名思义是：二分的栈（这不废话？）。
考虑在扫描 \(i\) 的时候动态维护 \(g_i\)，不妨设我们已经处理完 \(f\) 前 \(k-1\) 的值，那么就有两部：
- 有 \(g_k\) 更新 \(f_k\)，那么 \(f_k\) 就计算好了。
- 考虑 \(f_k\) 对后面的贡献，由于决策单调，所以在只计算 \(f\) 的前 \(k\) 个值的时候，\(f_k\) 一定是一段后缀，然后把这段后缀 \(g_i = k\) 即可。
例如，\(k=3\) 时，也许 \(g\) 数组的变化是：\(001112222 -> 001133333\)。
具体怎么找这个后缀的起点 \(x\)，是具有可二分性的，也许能得到一个 \(O(nlogn)\) 的线段树做法。
但是这样就不妙了，如果题目稍有转换，线段树写起来就不好写。
事实上，我们可以考虑用栈维护颜色连续段 \((l,r,k)\) 表示 \(k\) 这个点目前是 \(l\) 到 \(r\) 这个区间的决策点。
然后从后缀开始，暴力的检测这一个连续段是否被覆盖（就比如上面的例子，2的连续段就被3完全覆盖），如果被覆盖就弹栈。
最后还有一小段，就是一部分被新的所覆盖，一部分我自己还是决策点（就比如，1的连续段就被占据了一丢丢），那么这个分界点肯定也是有二分性的，所以直接二分就可以得到这个临界点，然后就稍微修改一下这一部分的覆盖范围，再插入新的连续段到栈顶即可。
这样就做到常数小的 \(O(nlogn)\)。
标签：二分,le,不等式,决策,dp,四边形,单调 From： https://www.cnblogs.com/wangzhongyuan/p/17958651