Slope Trick 优化

函数 $f:\mathbf Z\rightarrow\mathbf R\cup\{\pm\infty\}$ 是凸的，当且仅当

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

这个命题是凸函数的斜率刻画的简单推论．

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

这就是上述条件．

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

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

设 $S$ 为 $\mathbf R$ 或它的离散子集，则函数 $f:S\rightarrow\mathbf R\cup\{\pm\infty\}$ 为凸函数，当且仅当斜率

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

对于 $\mathbf R$ 上的函数 $f(x)$ 以及 $x_1<x_2$，对于 $\alpha\in(0,1)$，令 $x_3=\alpha x_1+(1-\alpha)x_2$，那么

就等价于

这两侧的不等式都等价于 $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}$，该不等式显然成立．否则，有

根据 $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}$ 成立，则有

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

函数 $f:\mathbf R\rightarrow\mathbf R\cup\{\pm\infty\}$ 是凸函数，当且仅当 $\operatorname{epi}f$ 是 $\mathbf R^2$ 内的凸集．

如果 $f$ 是凸函数，那么对于 $(x_1,y_1),(x_2,y_2)\in\operatorname{epi}f$ 和任意 $\alpha\in(0,1)$，有

所以，$\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 f(x_1)+(1-\alpha)f(x_2)\ge f\left(\alpha x_1+(1-\alpha)x_2\right)$，即 $f$ 的凸性．

设 $f,g$ 都是凸函数，$h$ 是它们的卷积下确界．设 $x_1<x_2$，且 $\alpha\in(0,1)$．根据卷积下确界的定义，对任意 $\varepsilon>0$，存在 $y_i,z_i\in\mathbf R$ 使得 $y_i+z_i=x_i$ 且

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

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

这就得到 $h$ 的凸性．

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

其中，$\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$ 且

故而，$(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_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$ 都是正常凸函数且 下半连续．对于算法竞赛的应用来说，这已经足够了，比如分段线性函数总是满足这些条件的．

首先，$\{b_i\}$ 严格递增，等价于 $\{b'_i\}=\{b_i-i\}$ 弱增．因此，可以对 $\{a'_i\}=\{a_i-i\}$ 求出差值最小的弱增序列 $\{b'_i\}=\{b_i-i\}$ 再恢复成序列 $\{b_i\}$ 即可．

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

容易得到状态转移方程为

初始状态为 $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}(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)$．

#include <iostream>
#include <queue>
#include <vector>

int main() {
  int n;
  std::cin >> n;
  std::vector<int> a(n), b(n);
  for (int& x : a) std::cin >> x;
  for (int i = 0; i < n; ++i) a[i] -= i;
  long long res = 0;
  std::priority_queue<int> max_heap;
  for (int i = 0; i < n; ++i) {
    max_heap.emplace(a[i]);
    max_heap.emplace(a[i]);
    res += max_heap.top() - a[i];
    max_heap.pop();
    b[i] = max_heap.top();
  }
  std::cout << res << '\n';
  for (int i = n - 2; i >= 0; --i) b[i] = std::min(b[i], b[i + 1]);
  for (int i = 0; i < n; ++i)
    std::cout << (b[i] + i) << (i == n - 1 ? '\n' : ' ');
  return 0;
}

首先考虑朴素 DP 解法．设 $f_i(x)$ 为第 $i$ 天结束时持有股票数量为 $x\ge 0$ 的最大利润，则

初始状态为 $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)$．

#include <iostream>
#include <queue>
#include <vector>

int main() {
  int n;
  std::cin >> n;
  std::vector<int> a(n);
  for (int& x : a) std::cin >> x;
  long long res = 0;
  std::priority_queue<int> max_heap;
  for (int x : a) {
    max_heap.emplace(-x);
    max_heap.emplace(-x);
    res += x + max_heap.top();
    max_heap.pop();
  }
  std::cout << res << '\n';
  return 0;
}

考虑朴素 DP 解法．设 $f_i(x)$ 为满足前 $i$ 个花园需求且净剩余 $x$ 单位泥土运到后面的花园时的最小代价．如果 $x<0$，就相当于净亏空 $|x|$ 单位泥土需要从后面的花园运送过来．那么，可以写成状态转移方程为

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

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

• 之前 $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\})$．

#include <iostream>
#include <stack>

int main() {
  int n;
  long long x, y, z;
  std::cin >> n >> x >> y >> z;
  std::stack<long long> neg, pos;
  long long lt = 0, rt = 0;
  long long res = 0;
  for (; n; --n) {
    int a, b;
    std::cin >> a >> b;
    lt -= z;
    rt += z;
    for (; b < a; ++b) {
      auto l = -y;
      if (!neg.empty()) {
        l = std::max(l, neg.top() + lt);
        neg.pop();
      }
      pos.emplace(l - rt);
      res -= l;
    }
    for (; b > a; --b) {
      auto r = x;
      if (!pos.empty()) {
        r = std::min(r, pos.top() + rt);
        pos.pop();
      }
      neg.emplace(r - lt);
      res += r;
    }
  }
  std::cout << res << std::endl;
  return 0;
}