【学习笔记】斜率优化、带权二分、决策单调性
把「带权二分」并过来了，都是和斜率有千丝万缕关系的家伙们 =w=
斜率优化
整理 dp 柿子后得到一个「斜率、截距是当前项，$x$、$y$ 坐标是之前项」的类一次函数柿子。根据截距的正负考虑维护什么方向的凸包。
举个例子：$dp_i = \max( dp_j + \frac{i - j}{i} )$，整理得 $(dp_j + 1) i - dp_i i = j$，截距项是 $-dp_i * i$，而我们要 $dp_i$ 尽量大，截距尽量小，即 $0$ 处取值尽量小，感性理解是直线尽量低，所以维护 $(dp_j + 1, j)$ 的下凸包，用斜率为 $i$ 的直线去切。
一道不错的题：$UOJ430-line$
朴素 dp 方程：$f_i = \min\limits_{l_i \leq j < i}( \max( t_{j + 1}, \cdots, t_i ) * suf_{i + 1} + f_j )$
考虑 cdq 分治计算 $f$，即递归处理好 $[l, mid]$ 再算 $[l, mid]$ 对 $[mid + 1, r]$ 的贡献，再递归处理 $[mid + 1, r]$。
这个 $max$ 得拆：
$max \in [mid + 1, r]$
$\max(t_{j + 1}, \cdots, t_{mid})$ 需要 $\leq max$，显然 $j$ 的位置单调不升，只要取左边的 $\min(f)$ 即可。
$max \in [l, mid]$
设 $max$ 在 $j(j \in [l, mid])$ 处取到。$j$ 处 $-max * suf_{i + 1} + f_i = f_{j - 1}$。
要 $f_i$ 最小就是截距最小。线段树维护下凸包，询问时每个区间二分求切点；然而如果离线将询问按 $suf$ 升序排列，就有单调性了，一路切过去就行了，少一只 $log$。所以最后是 $O(nlogn)$ 的！
人傻了，$AB * AC > 0$（叉积）表示三角形 ABC 为逆时针。xml 记错了，浪费一小时拼命撕烤，特此记录。
带权二分
这玩意儿其实早几个月就学了，现在来补笔记。
带权二分又称 wqs 二分，解决的是这样一类问题：有 $n$ 个物品，需要在强制选 $K$ 个物品的前提下最大/最小化代价；设强制选 $K$ 个的代价最值为 $val(K)$，$val(K)$ 无法直接求得，但是 $val$ 函数的最值以及取到最值的位置可以求，并且 $val$ 是一个凸函数。
现在讨论求上凸函数最大值（下凸函数最小值一个道理）。令 $f(x) = val(x) + kx$，$k$ 的实际意义是「多选一个物品就要付出的代价」，在坐标系上就是将 $val$ 的导函数向上平移了 $k$。导函数与 $x$ 轴的交点对应的就是 $val$ 的最高点，且上凸函数的导函数递减，因此 $k$ 变大，最值点右移，可二分。最后让 $val(K) = f(K) - kx$。
求下凸函数最小值，$k$ 变大，最值点左移
调边界是真的恶心，zbl
二分物品额外代价的时候还有可能跳过正确答案，这时如果答案的 $k$ 是一段连续区间，维护区间并判断即可。
如果不用输出方案，直接记录斜率，输出答案时乘一下。
决策单调性
作为感性理解的忠实爱好者…… 笔者只能用感性的语言来讲述它啦qwq！大概就是如果存在 $r_0$ 使得对于 $l_1 < l_2$，$l_1$ 优于 $l_2$，那么所有 $r \geq r_0$ 都满足 $l_1$ 优于 $l_2$。也就是说决策点（转移来源）分段且来源的位置单调增。决策单调性的有无，显然取决于价值函数。（废话）
以$CF321E$为例，$dp_{i, j} = \min( dp_{i - 1, k - 1} + val(k, j) )$，若对于 $k_1 < k_2$, $dp_{i - 1, k_1 - 1} + val(k_1, j) > dp_{i - 1, k_2 - 1} + val(k_2, j)$，那么随着 $i$ 增加，$val(k_1, j)$ 永远大于 $val(k_2, j)$，$k_2$ 永远优于 $k_1$。
再以 $JOI-$蛋糕拼接3 为例，$ans = \sum V_i - 2 * ( C_M - C_1 )$。对于 $l_1 < l_2$，感性理解新加入一个 $r$ 对 $l_1$ 产生的收益小于等于 $l_2$（$C$ 之差！），即，若对于 $r_0$，$l_2$ 优于 $l_1$，那么对于 $r \geq r_0$，$l_2$ 都优于 $l_1$。这就是决策单调性的定义。
编写大概有几种方式：
- 分治，$solve(l, r, L, R)$ 表示处理 $[l, r]$ 的 dp 值，决策点位置锁定在 $[L, R]$，每次找到 $mid = \frac{l + r}{2}$ 的决策点并递归，一只 $log$
- 二分 + 单调队列，单调队列维护决策点，他们的影响区间可以二分求，每次进来新决策点先看看能不能弹队尾，不能再二分求新决策点的影响区间（诗人小 G 那题好像就是这个）（上面那道 $321E$ 代码在这：点我）
四边形不等式笔者还没学会…… 主要是从没遇到过 感觉上面这些就能畅行天下了 qaq
考场上当然都是先猜后证啦 =w=