这就等价于 αf(x1)+(1−α)f(x2)≥f(αx1+(1−α)x2)，即 f 的凸性。
稍后会看到，利用上境图，可以将凸函数的卷积下确界与凸集的 Minkowski 和联系起来。
凸函数的变换
紧接着，本文介绍一些 Slope Trick 中经常遇见的保持凸性的变换。
非负线性组合
对于凸函数 f 和 g 以及非负实数 α,β≥0，函数 αf+βg 也是凸函数。而且，
Δ(αf+βg)=αΔf+βΔg.
因此，如果维护了凸函数 f 和 g 的斜率，要得到它们的非负线性组合 αf+βg 的斜率，只需要逐段计算即可。
在维护斜率的问题中，往往其中一个函数的形式比较简单，此时可以通过懒标记的方式降低修改复杂度。在维护拐点的问题中，要计算 f+g 的斜率拐点，只需要将 f 和 g 的斜率拐点合并即可。
卷积下确界（Minkowski 和）
凸函数的另一种常见操作是卷积下确界。对于函数 f 和 g，函数
h(x)=y∈Rinff(y)+g(x−y)
称为 f 和 g 的 卷积下确界2（infimal convolution）。如果 f 和 g 都是凸函数，它们的卷积下确界也是凸函数。
对图示的解释
如图所示，要求 f 和 g 的卷积下确界 h，可以将 f 的图像（第三个图的红色虚线）上的每一个点都视作原点，在相应的坐标系内画出 g 的图像（第三个图中的蓝色虚线）。当坐标系原点沿着 f 的图像移动时，g 的图像（上境图）移动的轨迹轮廓（即下凸壳），就是 h 的图像。可以看出，h 的每一个斜率段，都要么是 f 的斜率段，要么是 g 的斜率段：只是重新按照斜率大小排序了。这个过程中，f 和 g 的角色可以互换，即让 f 的图像沿着 g 的图像移动，得到的结果是一致的。
几何直观上，epih 就是 epif 和 epig 的 Minkowski 和。如果 f 和 g 都是分段线性函数，那么 h 同样是分段线性函数，且它的斜率段可以看作是 f 和 g 的斜率段合并（再排序）的结果。
#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;}
#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;}
#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;}
给定长度为 n 的序列 {ai} 和 {bi}，分别表示第 i 个花园已经有的泥土数量和需要的泥土数量（不能多也不能少）。购买一单位泥土放入任意花园价格为 X，从任意花园运走一单位泥土价格为 Y，从花园 i 向花园 j 运送一单位泥土价格为 Z∣i−j∣。求满足所有花园需求的最小成本。（ai,bi≤10）
解答
考虑朴素 DP 解法。设 fi(x) 为满足前 i 个花园需求且净剩余 x 单位泥土运到后面的花园时的最小代价。如果 x<0，就相当于净亏空 ∣x∣ 单位泥土需要从后面的花园运送过来。那么，可以写成状态转移方程为
fi(x)=y∈Rminfi−1(y)+∣y∣Z+h((x−y)+(bi−ai)).
其中，函数 h(δ) 表示当前花园的泥土净购买量为 δ 时的成本，即
h(δ)=max{0,δ}X+max{0,−δ}Y=max{δX,−δY}.
它显然是凸函数。该状态转移方程的含义为
之前 i−1 个花园净剩余泥土数量为 y 时，最小成本为 fi−1(y)；
将净剩余（亏空）的泥土数量在 i 与 i−1 之间运送的成本为 ∣y∣Z；
通过买卖，将第 i 个花园的泥土数量从 ai 调整为 bi，并将净剩余泥土数量从 y 调整到 x，最小成本为 h((x−y)+(bi−ai))。
原题中 ai 和 bi 很小，因此只需要维护若干个长度为 1 的斜率段即可。虽然斜率段有无穷多个，但是有上界 X 和下界 −Y，且严格位于两者之间的斜率段数目并不多。因为不涉及插入操作，所以可以用两个栈维护原点两侧的斜率段，区间加和区间最值操作全部打懒标记完成。上述三步操作分别对应：
对左右两个栈分别打懒标记，左侧加 −Z，右侧加 Z；
每次栈内弹出元素时，都对 −Y 取最大值，对 X 取最小值。如果左栈为空，则弹出 −Y。如果右栈为空，则弹出 X；
将左栈顶部的 (bi−ai) 个元素弹出，插入右栈；当然，bi−ai<0 时，就反过来。
在交换栈顶时，更新答案，向左移动就减去当前斜率，向右移动就加上当前斜率。
算法复杂度为 O(nmax{ai,bi})。
#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;}