「Note」关于斜率优化维护内容的推导

追求乱搞科学严谨证明，拒绝对于 不等号方向 与 单调 队列 / 栈 的排列组合。

哈哈哈，今天上台直接乱说，好像以前都是盲猜单调队列维护下凸壳过的。。。

约定

对于一般形式 $T(j_1, j_2) \le /\geq g(i)$ 中 $g(i)$ 有单调性的情况进行讨论。
结合图像还是很清晰的。

$\mathrm{I}. \ T(j_1, j_2) \le g(i), g(i) \uparrow$

$g(i)$ 斜率一直变大，最优的决策点即是让 $g(i)$ 在 $y$ 轴上截距最小，移动过程中发现 $j_4$ 显然不可能成为决策点。所以应该维护一个下凸壳。
于是我们维护的数据结构里的东西满足下面的关系。
$T(j_1, j_2) \le T(j_2, j_3) \le T(j_4, j_5) \le \dots \le T(j_{k - 1}, j_k) \le g(i)$。
那么可以发现，越靠前的决策点越不可能成为切点，于是我们应该从头将决策点弹出，所以是单调队列。

$\mathrm{II}. \ T(j_1, j_2) \le g(i), g(i) \downarrow$

$g(i)$ 斜率一直变小，最优的决策点即是让 $g(i)$ 在 $y$ 轴上截距最小，移动过程中发现 $j_4$ 显然不可能成为决策点。所以应该维护一个下凸壳。
于是我们维护的数据结构里的东西满足下面的关系。
$T(j_1, j_2) \le T(j_2, j_3) \le T(j_4, j_5) \le \dots \le T(j_{k - 1}, j_k) \le g(i)$。
然后看出来在 $g(i)$ 一开始时，斜率很大 $j_3$ 是一个很优的决策点，但是当斜率变小之后，在 $j_3$ 之前的 $j_2$ 会优于 $j_3$，这时从尾把 $j_3$ 弹出，可以看出，斜率变得更小时，$j_3$ 只会更劣，弹出 $j_3$ 不影响正确性，所以我们应该维护一个单调栈。

$\mathrm{III}. \ T(j_1, j_2) \ge g(i), g(i) \uparrow$

$g(i)$ 斜率一直变大，最优的决策点即是让 $g(i)$ 在 $y$ 轴上截距最大，移动过程中发现 $j_2$ 显然不可能成为决策点。所以应该维护一个上凸壳。
于是我们维护的数据结构里的东西满足下面的关系。
$T(j_1, j_2) \ge T(j_2, j_3) \ge T(j_4, j_5) \ge \dots \ge T(j_{k - 1}, j_k) \ge g(i)$。
观察图像可以发现，在斜率比较小的时候，$j_3$ 是一个很优的决策点，但是当斜率变大时，前面的 $j_4$ 会替代掉 $j_3$，并且我们可以肯定，在斜率越来越大时，$j_4$ 一定优于 $j_3$，所以可以把 $j_3$ 从尾部弹出，我们应该维护一个单调栈。

$\mathrm{IV}. \ T(j_1, j_2) \ge g(i), g(i) \downarrow$

$g(i)$ 斜率一直变小，最优的决策点即是让 $g(i)$ 在 $y$ 轴上截距最大，移动过程中发现 $j_2$ 显然不可能成为决策点。所以应该维护一个上凸壳。
于是我们维护的数据结构里的东西满足下面的关系。
$T(j_1, j_2) \ge T(j_2, j_3) \ge T(j_4, j_5) \ge \dots \ge T(j_{k - 1}, j_k) \ge g(i)$。
可以看到，斜率很大时 $j_1$ 是最优的，当斜率在变小后，右上角的 $j_4$ 会比 $j_1$ 更优，并且在斜率不断变小中，$j_4$ 永远比 $j_1$ 优。