Slope Trick

$$
f(\alpha x+(1-\alpha)y) \le \alpha f(x)+(1-\alpha)f(y),
$$

就称函数 $f$ 为 **凸函数**（convex function），其中 $\pm\infty$ 的运算法则规定为 $\pm\infty$ 乘以任何正实数或是加上任何实数都等于其自身，且对于任何实数 $x\in\mathbf R$ 都有 $-\infty<x<+\infty$．

1.  常数函数：$f(x)=c$，其中 $c\in\mathbf R$；
2.  一次函数：$f(x)=kx+b$，其中 $k,b\in\mathbf R$ 且 $k\neq 0$；
3.  绝对值函数：$f(x)=|x-a|$，其中 $a\in\mathbf R$；
4.  任何凸函数限制在某个区间上的结果，例如 $0_{[a,b]}(x)$（在凸分析的语境下也称作 $[a,b]$ 的指示函数）．

-   当 $x\in S$ 时，$\tilde f(x)=f(x)$，
-   当 $x\in(\inf S,\sup S)\setminus S$ 时，设 $s_-=\max\{s\in S:s\le x\}$，$s_+=\min\{s\in S:s\ge x\}$，则

    $$
    \tilde f(x) = \dfrac{s_+-x}{s_+-s_-}f(s_-)+\dfrac{x-s_-}{s_+-s_-}f(s_+),
    $$
-   当 $x\notin[\inf S,\sup S]$ 时，$\tilde f(x)=+\infty$．

那么，如果 $\tilde f(x)$ 是 $\mathbf R$ 上的凸函数，就称 $f(x)$ 是 $S$ 上的 **凸函数**．

$$
f(x)-f(x-1)\le f(x+1)-f(x)
$$

对于所有 $x\in\mathbf Z$ 都成立．

如果 $f$ 是 $\mathbf Z$ 上的凸函数，那么根据斜率弱增，有

$$
\Delta f(x-1,x)\le \Delta f(x-1,x+1) \le\Delta f(x,x+1).
$$

这就是上述条件．

反过来，如果上述条件成立，那么对于任何 $x_1<x_2$，都有

$$
\Delta f(x_1,x_2) = \dfrac{1}{x_2-x_1}\sum_{i=x_1}^{x_2-1}\left(f(i)-f(i-1)\right).
$$

这相当于对所有满足 $x_1\le i<x_2$ 的差分的算术平均值．如果 $x_2$ 增加一，就相当于插入一项更大的差分；如果 $x_1$ 增加一，就相当于移除一项最小的差分．这两个操作都会使得平均值上升．这就说明斜率 $\Delta f(x_1,x_2)$ 弱增，即 $f$ 是 $\mathbf Z$ 上的凸函数．

$$
\Delta f(x_1,x_2) = \dfrac{f(x_2)-f(x_1)}{x_2-x_1}
$$

对于任何 $x_1,x_2\in S$ 且 $x_1<x_2$ 都是 $x_1$ 和 $x_2$ 的弱增函数．

$$
\Delta f(x_1,x_3) \le \Delta f(x_1,x_2) \le \Delta f(x_3,x_2)
$$

就等价于

$$
\dfrac{f(x_3)-f(x_1)}{1-\alpha} \le f(x_2)-f(x_1) \le \dfrac{f(x_2)-f(x_3)}{\alpha}.
$$

这两侧的不等式都等价于 $f(x_3)\le\alpha f(x_1)+(1-\alpha)f(x_2)$，即函数 $f(x)$ 的凸性．

对于 $\mathbf R$ 的离散子集 $S$ 上的函数 $f(x)$，斜率弱增这一条件的必要性可以由 $\tilde f(x)$ 的凸性推导出来．现在要证明它的充分性，为此只要证明 $\Delta\tilde f(x_1,x_2)$ 也是弱增的．设 $S=\{s_i\}$ 且 $s_i$ 关于 $i$ 严格递增，并设 $s_{i_1}\le x_1\le s_{i_1+1}$ 且 $s_{i_2}\le x_2\le s_{i_2+1}$，自然有 $i_1\le i_2$．令 $\Delta_i=\Delta f(s_i,s_{i+1})$，那么，可以证明 $\Delta_{i_1}\le\Delta\tilde f(x_1,x_2)\le\Delta_{i_2}$．

这分两种情形．如果 $i_1=i_2$，那么 $\Delta_{i_1}=\Delta\tilde f(x_1,x_2)=\Delta_{i_2}$，该不等式显然成立．否则，有

$$
\Delta\tilde f(x_1,x_2) = \dfrac{1}{x_2-x_1}\left((s_{i_1+1}-x_1)\Delta_{i_1}+(x_2-s_{i_2})\Delta_{i_2}+\sum_{j=i_1+1}^{i_2-1}(s_{j+1}-s_j)\Delta_j\right).
$$

根据 $S$ 上的斜率递增可知，$\Delta_i$ 关于 $i$ 递增，所以，$\Delta_{i_1}\le\Delta\tilde f(x_1,x_2)\le\Delta_{i_2}$．

利用这个结论，对于 $x_1<x_2$ 和 $\alpha\in(0,1)$，令 $x_3=\alpha x_1+(1-\alpha)x_2$，并取 $i_3$ 使得 $s_{i_3}\le x_3\le s_{i_3+1}$ 成立，则有

$$
\Delta\tilde f(x_1,x_3) \le \Delta_{i_3} \le \Delta\tilde f(x_3,x_2).
$$

代入 $x_3$ 的表达式，就得到 $\tilde f(x)$ 的凸性．

$$
\alpha y_1+(1-\alpha)y_2 \ge \alpha f(x_1)+(1-\alpha)f(x_2) \ge f(\alpha x_1+(1-\alpha) x_2).
$$

所以，$\alpha(x_1,y_1)+(1-\alpha)(x_2,y_2)\in\operatorname{epi}f$．

反过来，如果 $\operatorname{epi}f$ 是凸集，那么对于任意 $x_1<x_2$ 以及 $\alpha\in(0,1)$，有

$$
\alpha(x_1,f(x_1))+(1-\alpha)(x_2,f(x_2)) \in \operatorname{epi}f.
$$

这就等价于 $\alpha f(x_1)+(1-\alpha)f(x_2)\ge f\left(\alpha x_1+(1-\alpha)x_2\right)$，即 $f$ 的凸性．

$$
h(x_i) + \varepsilon > f(y_i) + g(z_i).
$$

故而，结合 $f,g$ 的凸性及 $h$ 的定义，有

$$
\begin{aligned}
\alpha h(x_1)+(1-\alpha)h(x_2) + \varepsilon 
&> \alpha f(y_1) + (1-\alpha) f(y_2) + \alpha g(z_1) + (1-\alpha) g(z_2)\\
&\ge f\left(\alpha y_1+(1-\alpha)y_2\right) + g\left(\alpha z_1+(1-\alpha)z_2\right)\\
&\ge h(\alpha x_1+(1-\alpha)x_2).
\end{aligned}
$$

因为 $\varepsilon>0$ 是任意选取的，所以

$$
\alpha h(x_1)+(1-\alpha)h(x_2) \ge h(\alpha x_1+(1-\alpha)x_2).
$$

这就得到 $h$ 的凸性．

然后，对于几何直观，严格地说，只能证明如下结论：

$$
\operatorname{epi} f + \operatorname{epi} g\subseteq \operatorname{epi}h \subseteq \operatorname{cl}(\operatorname{epi} f + \operatorname{epi} g).
$$

其中，$\operatorname{cl}$ 表示闭包．

对于任何 $(x,y)\in\operatorname{epi} f + \operatorname{epi} g$，都存在 $(x_1,y_1)\in\operatorname{epi} f$ 且 $(x_2,y_2)\in\operatorname{epi} g$，使得 $x=x_1+x_2$ 且

$$
y = y_1+y_2 \ge f(x_1)+g(x_2) \ge h(x_1+x_2)=h(x).
$$

故而，$(x,y)\in\operatorname{epi}h$．这说明 $\operatorname{epi} f + \operatorname{epi} g\subseteq \operatorname{epi}h$．

反过来，对于任何 $(x,y)\in\operatorname{epi}h$，有 $y\ge h(x)$．根据 $h$ 的定义，对任何 $\varepsilon>0$，都存在 $x_1+x_2=x$ 使得

$$
y + \varepsilon > f(x_1) + g(x_2).
$$

令 $y_1=f(x_1)$ 且 $y_2=g(x_2)$，就有 $y+\varepsilon>y_1+y_2$．这说明，对于任何 $\varepsilon>0$，都有 $(x_1,y_1)+(x_2,y_2)\in\operatorname{epi} f + \operatorname{epi} g$ 位于点 $(x,y)$ 与点 $(x,y+\varepsilon)$ 的连线上．取 $\varepsilon\rightarrow 0$，就有 $\operatorname{epi}h \subseteq \operatorname{cl}(\operatorname{epi} f + \operatorname{epi} g)$．

所以，$\operatorname{epi} f + \operatorname{epi} g = \operatorname{epi}h$ 当且仅当它是闭凸集．一个使其满足的条件是，$f$ 和 $g$ 都是正常凸函数且 [下半连续](https://en.wikipedia.org/wiki/Semi-continuity)．对于算法竞赛的应用来说，这已经足够了，比如分段线性函数总是满足这些条件的．

    $$
    f(x) = \min_{y\in\mathbf R}g(y) + 0_{[-b,-a]}(x-y).
    $$
-   $f(x)=\min\{g(x-a_i)+b_i\}$ 是 $\mathbf Z$ 上的凸函数，只要 $g(x)$ 是 $\mathbf Z$ 上的凸函数，且在有限集合 $\{a_i\}\subset\mathbf Z$ 上定义的函数 $h:a_i\mapsto b_i$ 也是该离散集合上的凸函数．这是因为延拓之后的函数 $\tilde f(x)$ 可以看作是卷积下确界：

    $$
    \tilde f(x) = \min_{y\in\mathbf R}\tilde h(y)+\tilde g(x-y).
    $$

    因此，延拓之前的函数 $f(x)$ 也是凸函数．

考虑朴素 DP 解法．设 $f_i(x)$ 是已经选取了序列 $\{b'_i\}$ 中前 $i$ 个数字，且第 $i$ 个数字不超过 $x$ 时，已经选取的数字与 $\{a'_i\}$ 的前 $i$ 个数字的最小差值：

$$
f_i(x) = \min\sum_{j=1}^i|a'_j-b'_j|\text{ s.t. }b'_1\le b'_2\le\cdots\le b'_i\le x.
$$

容易得到状态转移方程为

$$
f_i(x) = \min_{y\le x}f_{i-1}(y)+|a'_i-y|.
$$

初始状态为 $f_0(x)\equiv 0$，最后要求的就是 $\min_xf_n(x)$．利用前文提到的凸函数的变换，从 $f_{i-1}(x)$ 到 $f_i(x)$，需要经过两步变换：

1.  首先，加上 $|a'_i-x|$，这相当于对区间 $(-\infty,a'_i]$ 内的所有斜率段都增加 $-1$，对区间 $[a'_i,+\infty)$ 内的所有斜率段都增加 $1$；
2.  对得到的函数取最小值，将 $g(x)=f_{i-1}(x)+|a'_i-x|$ 变为 $f_i(x)=\min_{y\le x}g(y)$．根据前文分析，这相当于对 $g(x)$ 和 $0_{[0,+\infty)}$ 做卷积下确界．因为后者的斜率段只有一段，斜率为 $0$ 且向右延伸至无限长，将其插入 $g(x)$ 的斜率段中，相当于删除其中所有正斜率段．

明晰了这些操作后，已经可以直接用平衡树维护所有斜率段了，但代码较复杂．注意到问题中斜率每次变化至多 $1$，故而所有斜率段的绝对值都不超过 $n$．不直接维护斜率段，转而直接维护斜率拐点更为方便．

设 $f_{-1}(x)$ 的拐点集为 $\xi_{-k}\le\cdots\le\xi_{-1}\le\xi_{1}\le\cdots\le\xi_{\ell}$．那么，上面的两步操作分别对应：

1.  增加一个负斜率段的拐点 $a'_i$ 和一个正斜率段的拐点 $a'_i$；
2.  弹出所有正斜率段的拐点 $\xi_1,\cdots,\xi_{\ell}$．

实际维护时，因为每次操作结束后都没有正斜率段的拐点，即斜率拐点具有形式 $\xi_{-k}\le\cdots\le\xi_{-1}$，而且操作总发生在正负斜率段交界处，所以直接维护一个最大堆存储所有拐点即可．两步操作分别对应：

1.  插入两次 $a'_i$；
2.  弹出堆顶．

当然，每次结束后都需要维护当前函数的最小值．因为操作结束后，没有正斜率段，函数最小值就是它在最大堆堆顶处的取值．设每次操作之前堆顶为 $\xi_{-1}$，最小值为 $f_{i-1}(\xi_{-1})$．因为弹出的堆顶是正斜率段的最小拐点，函数的最小值就等于该处函数的取值，所以直接计算弹出前堆顶处函数的取值即可，亦即

$$
f_{i-1}(\max\{a'_i,\xi_{-1}\})+|\max\{a'_i,\xi_{-1}\}-a'_i|=f_{i-1}(\xi_{-1})+\max\{0,\xi_{-1}-a'_i\}.
$$

其中，第一项相等是因为 $f_{i-1}(x)$ 没有正斜率段．因此，每次只需要在最小值上不断累加 $\max\{0,\xi_{-1}-a'_i\}$ 即可．

本题还要求输出一种最优方案．因为最后操作结束时，最优解就是堆顶，所以 $b'_n$ 的取值可以直接确定．如果已经知道了第 $i$ 个最优解 $b'_i$，要求解 $f_{i-1}(x)$ 满足 $x\le b'$ 的最优解，只需要注意到因为 $f_{i-1}(x)$ 是凸的，所以越接近它的全局最小值点，解就越优，故而只要记录 $f_{i-1}(x)$ 的全局最小值点，并将它与 $b'_i$ 取最小值，就可以得到最优的 $b'_{i-1}$．

时间复杂度为 $O(n\log n)$．

```cpp
--8<-- "docs/dp/code/opt/slope-trick/sequence.cpp"
```

$$
f_i(x) = \min\sum_{j=1}^i|a_j-b_j|\text{ s.t. }|b_{j-1}-b_j|\le h,\forall 1<j\le i,~b_i=x.
$$

由此，有状态转移方程为

$$
f_i(x) = |a_i-x| + \min_{|y-x|\le h} f_{i-1}(y). 
$$

起始条件为 $f_0(x)\equiv 0$．最后要求的仍然是 $\min_xf_n(x)$．

状态转移拆解为对凸函数的操作，分两步：

1.  首先对 $f_{i-1}(x)$ 取最值，变为 $\min_{|y-x|\le h} f_{i-1}(y)$，这相当于 $f_{i-1}(x)$ 与 $0_{[-h,h]}(x)$ 的卷积下确界；
2.  再将得到的函数与 $|a_i-x|$ 相加．

同样因为斜率每次只变化一，可以考虑维护拐点．这样，这两步操作就可以描述为：

1.  将所有负斜率段向左移动 $h$，将所有正斜率段向右移动 $h$；
2.  插入两次 $a_i$．

显然，对于本题，将正负斜率段分别维护较为方便．因为操作主要集中在零斜率段附近，因此考虑使用 [对顶堆](../../ds/binary-heap.md#对顶堆)，即分别用最大堆和最小堆维护负斜率段和正斜率段的拐点．拐点的整体平移操作用懒标记完成．因为第二步操作需要分别对两个堆插入一个 $a_i$，而且，插入完成后，未必最大堆的堆顶仍然小于等于最小堆的堆顶．此时，交换两堆顶，直到堆顶的大小关系得到满足即可．

最后，考虑操作过程中如何更新最小值．因为第一步平移操作并不会改变最小值，所以只要考虑交换堆顶的操作即可．设 $\xi_{-1}>\xi_1$，将堆顶 $\xi_{-1}$ 与 $\xi_1$ 交换时，函数由

$$
\max\{0,x-\xi_{-1}\}+\max\{0,x-\xi_1\}
$$

变为

$$
\max\{0,x-\xi_{1}\}+\max\{0,x-\xi_{-1}\}.
$$

过程中，函数形状不变，只是向下平移了 $|\xi_{-1}-\xi_1|$．因此，要使得交换堆顶前后函数保持不变，只需要将最小值累加 $|\xi_{-1}-\xi_1|$ 即可．

算法的时间复杂度仍为 $O(n\log n)$，因为每次添加元素后，交换堆顶的操作至多执行一次．

```cpp
--8<-- "docs/dp/code/opt/slope-trick/safety.cpp"
```

$$
f_i(x) = \max\{f_{i-1}(x-1)-p_i,f_{i-1}(x),f_{i-1}(x+1)+p_i\}.
$$

初始状态为 $f_0(0)=0$，且对所有 $x\neq 0$，有 $f_0(x)=-\infty$．问题的答案就是 $f_n(0)$．

从 $f_{i-1}(x)$ 到 $f_i(x)$ 需要经过两步变换：

1.  将 $f_{i-1}(x)$ 与函数

    $$
    h_i(x) = \begin{cases}p_i,&x=-1,\\0,&x=0,\\-p_i,&x=1\end{cases}
    $$

    对应的分段线性函数 $\tilde h(x)$（显然是凹函数）做卷积上确界；
2.  因为这样会导致函数在区间 $[-1,0)$ 内具有有限值，这与 $x\ge 0$ 的要求矛盾，故而需要截取函数在 $[0,+\infty)$ 内的部分．

将它们转化为斜率段的变化，就是如下两步：

1.  插入长度为 $2$、斜率为 $-p_i$ 的斜率段；
2.  删除斜率有限的斜率段中，斜率最大且长度为 $1$ 的一段．

因为斜率段的长度总是自然数，所以不妨维护若干个长度为一的斜率段，从而只需要记录每段的斜率即可．因为只需要插入和访问最大值操作，所以只需要一个最大堆．操作分两步：

1.  插入两次 $-p_i$；
2.  弹出堆顶．

还需要维护 $f_i(0)$ 的值．因为第一步操作得到的函数在 $x=-1$ 处的取值就是 $f_{i-1}(0)+p_i$，所以它在 $x=0$ 处的取值就是该值加上马上要弹出的堆顶——它就是函数在区间 $[-1,0]$ 上的斜率．因为截断不改变函数在 $x=0$ 处的取值，所以这就是 $f_i(0)$．

对比该算法实现与上文 [最小成本递增序列](#例题最小成本递增序列) 的代码可知，该算法等价于求将股票价格变为弱递减序列的最小成本．

时间复杂度为 $O(n\log n)$．

```cpp
--8<-- "docs/dp/code/opt/slope-trick/stock.cpp"
```

$$
f_i(x) = \min_{y\in\mathbf R} f_{i-1}(y) + |y|Z + h((x-y)+(b_i-a_i)).
$$

其中，函数 $h(\delta)$ 表示当前花园的泥土净购买量为 $\delta$ 时的成本，即

$$
h(\delta) = \max\{0,\delta\}X + \max\{0,-\delta\}Y = \max\{\delta X,-\delta Y\}.
$$

它显然是凸函数．该状态转移方程的含义为

-   之前 $i-1$ 个花园净剩余泥土数量为 $y$ 时，最小成本为 $f_{i-1}(y)$；
-   将净剩余（亏空）的泥土数量在 $i$ 与 $i-1$ 之间运送的成本为 $|y|Z$；
-   通过买卖，将第 $i$ 个花园的泥土数量从 $a_i$ 调整为 $b_i$，并将净剩余泥土数量从 $y$ 调整到 $x$，最小成本为 $h((x-y)+(b_i-a_i))$．

初始状态为 $f_0(0)=0$，且对所有 $x\neq 0$，有 $f_0(x)=+\infty$．问题的答案就是 $f_n(0)$．

将函数 $f_{i-1}(x)$ 变换为 $f_i(x)$ 可以分为三步：

1.  首先，加上 $|x|Z$，得到 $f_{i-1}(x)+|x|Z$；
2.  然后，与 $h(x)$ 做卷积下确界，得到 $\min_{y\in\mathbf R}f_{i-1}(y)+|y|Z+h(x-y)$；
3.  最后，将函数向左平移 $(b_i-a_i)$ 个单位．

转化为对斜率段的操作，同样分为三步：

1.  将原点左侧斜率段全体加上 $-Z$，将原点右侧斜率段全体加上 $Z$；
2.  将所有小于 $-Y$ 的斜率段全部替换为 $-Y$，将所有大于 $X$ 的斜率段全部替换为 $X$；
3.  将所有斜率段向左平移 $(b_i-a_i)$ 个单位．

原题中 $a_i$ 和 $b_i$ 很小，因此只需要维护若干个长度为 $1$ 的斜率段即可．虽然斜率段有无穷多个，但是有上界 $X$ 和下界 $-Y$，且严格位于两者之间的斜率段数目并不多．因为不涉及插入操作，所以可以用两个栈维护原点两侧的斜率段，区间加和区间最值操作全部打懒标记完成．上述三步操作分别对应：

1.  对左右两个栈分别打懒标记，左侧加 $-Z$，右侧加 $Z$；
2.  每次栈内弹出元素时，都对 $-Y$ 取最大值，对 $X$ 取最小值．如果左栈为空，则弹出 $-Y$．如果右栈为空，则弹出 $X$；
3.  将左栈顶部的 $(b_i-a_i)$ 个元素弹出，插入右栈；当然，$b_i-a_i<0$ 时，就反过来．

在交换栈顶时，更新答案，向左移动就减去当前斜率，向右移动就加上当前斜率．

算法复杂度为 $O(n\max\{a_i,b_i\})$．

```cpp
--8<-- "docs/dp/code/opt/slope-trick/landscaping.cpp"
```