Slope Trick 优化

$\mathbf{Z}$ 上的凸函数的等价定义

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

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

对于所有 $x\in \mathbf{Z}$ 都成立。

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

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

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

这就是上述条件。

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

$$\mathrm{\Delta }f(x_1,x_2)=\frac{1}{x_2-x_1}\sum _{i=x_1}^{x_2-1}(f(i)-f(i-1)).$$

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

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

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

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

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

$$\mathrm{\Delta }f(x_1,x_3)\le \mathrm{\Delta }f(x_1,x_2)\le \mathrm{\Delta }f(x_3,x_2)$$

就等价于

$$\frac{f(x_3)-f(x_1)}{1-\alpha }\le f(x_2)-f(x_1)\le \frac{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)$ 的凸性推导出来。现在要证明它的充分性，为此只要证明 $\mathrm{\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$。令 ${\mathrm{\Delta }}_i=\mathrm{\Delta }f(s_i,s_{i+1})$，那么，可以证明 ${\mathrm{\Delta }}_{i_1}\le \mathrm{\Delta }\tilde{f}(x_1,x_2)\le {\mathrm{\Delta }}_{i_2}$。

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

$$\mathrm{\Delta }\tilde{f}(x_1,x_2)=\frac{1}{x_2-x_1}((s_{i_1+1}-x_1){\mathrm{\Delta }}_{i_1}+(x_2-s_{i_2}){\mathrm{\Delta }}_{i_2}+\sum _{j=i_1+1}^{i_2-1}(s_{j+1}-s_j){\mathrm{\Delta }}_j).$$

根据 $S$ 上的斜率递增可知，${\mathrm{\Delta }}_i$ 关于 $i$ 递增，所以，${\mathrm{\Delta }}_{i_1}\le \mathrm{\Delta }\tilde{f}(x_1,x_2)\le {\mathrm{\Delta }}_{i_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}$ 成立，则有

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

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

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

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

$$\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 \mathrm{epi}f$。

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

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

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

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

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

因为 是任意选取的，所以

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

这就得到 $h$ 的凸性。

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

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

其中，$\mathrm{cl}$ 表示闭包。

对于任何 $(x,y)\in \mathrm{epi}f+\mathrm{epi}g$，都存在 $(x_1,y_1)\in \mathrm{epi}f$ 且 $(x_2,y_2)\in \mathrm{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 \mathrm{epi}h$。这说明 $\mathrm{epi}f+\mathrm{epi}g\subseteq \mathrm{epi}h$。

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

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

所以，$\mathrm{epi}f+\mathrm{epi}g=\mathrm{epi}h$ 当且仅当它是闭凸集。一个使其满足的条件是，$f$ 和 $g$ 都是正常凸函数且 下半连续。对于算法竞赛的应用来说，这已经足够了，比如分段线性函数总是满足这些条件的。

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

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

$$f_i(x)=min\sum _{j=1}^i|a_j^{\prime }-b_j^{\prime }|\text{ s.t. }{b}_1^{\prime }\le b_2^{\prime }\le \cdots \le b_i^{\prime }\le x.$$

容易得到状态转移方程为

$$f_i(x)=\underset{y\le x}{min}{f}_{i-1}(y)+|a_i^{\prime }-y|.$$

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

1. 首先，加上 $|a_i^{\prime }-x|$，这相当于对区间 $(-\mathrm{\infty },a_i^{\prime }]$ 内的所有斜率段都增加 $-1$，对区间 $[a_i^{\prime },+\mathrm{\infty })$ 内的所有斜率段都增加 $1$；
2. 对得到的函数取最小值，将 $g(x)=f_{i-1}(x)+|a_i^{\prime }-x|$ 变为 $f_i(x)=\underset{y\le x}{min}g(y)$。根据前文分析，这相当于对 $g(x)$ 和 $0_{[0,+\mathrm{\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^{\prime }$ 和一个正斜率段的拐点 $a_i^{\prime }$；
2. 弹出所有正斜率段的拐点 ${\xi }_1,\cdots ,{\xi }_{\ell }$。

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

1. 插入两次 $a_i^{\prime }$；
2. 弹出堆顶。

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

$$f_{i-1}(max\{a_i^{\prime },{\xi }_{-1}\})+|max\{a_i^{\prime },{\xi }_{-1}\}-a_i^{\prime }|=f_{i-1}({\xi }_{-1})+max\{0,{\xi }_{-1}-a_i^{\prime }\}.$$

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

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

#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;
}

内容大致与上一个题目相仿，只是序列 $\{b_i\}$ 的限制发生了变化。同样地，设 $f_i(x)$ 为第 $i$ 个数字取 $x$ 时，前 $i$ 个数字的差值的最小值：

由此，有状态转移方程为

$$f_i(x)=|a_i-x|+\underset{|y-x|\le h}{min}{f}_{i-1}(y).$$

起始条件为 $f_0(x)\equiv 0$。最后要求的仍然是 $\underset{x}{min}{f}_n(x)$。

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

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

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

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

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

最后，考虑操作过程中如何更新最小值。因为第一步平移操作并不会改变最小值，所以只要考虑交换堆顶的操作即可。设 ，将堆顶 ${\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)$，因为每次添加元素后，交换堆顶的操作至多执行一次。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

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

int main() {
  int n;
  long long h;
  std::cin >> n >> h;
  std::priority_queue<long long> max_heap;
  std::priority_queue<long long, std::vector<long long>, std::greater<>>
      min_heap;
  long long lt = 0, rt = 0;
  long long res = 0;
  for (; n; --n) {
    long long x;
    std::cin >> x;
    lt += h;
    rt += h;
    max_heap.emplace(x + lt);
    min_heap.emplace(x - rt);
    auto l = max_heap.top() - lt;
    auto r = min_heap.top() + rt;
    while (l > r) {
      max_heap.pop();
      min_heap.pop();
      res += l - r;
      max_heap.emplace(r + lt);
      min_heap.emplace(l - rt);
      l = max_heap.top() - lt;
      r = min_heap.top() + rt;
    }
  }
  std::cout << res << std::endl;
  return 0;
}

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

$$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\ne 0$，有 $f_0(x)=-\mathrm{\infty }$。问题的答案就是 $f_n(0)$。

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

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

   

   对应的分段线性函数 $\tilde{h}(x)$（显然是凹函数）做卷积上确界；

2. 因为这样会导致函数在区间 $[-1,0)$ 内具有有限值，这与 $x\ge 0$ 的要求矛盾，故而需要截取函数在 $[0,+\mathrm{\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)$。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

#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|$ 单位泥土需要从后面的花园运送过来。那么，可以写成状态转移方程为

$$f_i(x)=\underset{y\in \mathbf{R}}{min}{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\ne 0$，有 $f_0(x)=+\mathrm{\infty }$。问题的答案就是 $f_n(0)$。

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

1. 首先，加上 $|x|Z$，得到 $f_{i-1}(x)+|x|Z$；
2. 然后，与 $h(x)$ 做卷积下确界，得到 $\underset{y\in \mathbf{R}}{min}{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)$ 个元素弹出，插入右栈；当然， 时，就反过来。

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

算法复杂度为 $O(nmax\{a_i,b_i\})$。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

#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;
}