.png)
缘起
该部分为废话，不想看的话可以直接跳过。
高考集训，主包按照课件整理出了一个足足有 44 题且蓝紫紫的洛谷题单。
是令本蒟蒻两眼一黑的程度。
但是里面有一道题：CF865D。
这是道蓝，但是其实还是蛮简单的十几行代码就水过去了。
主包顺着讨论区的指引，发现了六倍经验！于是挨个水题，前五道都比较顺利，但是败在了 P4331 上。
这个蒟蒻终于发现自己在对算法一无所知的情况下硬水了五道题。。。
于是，刷题暂停，让我先看看到底怎么个事。
六倍经验分别为 CF713C、CF13C、P4597、P2893、P4331、CF865D。
六倍经验原帖
前置知识：凸函数（convex function）& 凹函数（concave function）
以免你不知道你知道的凸函数是不是我说的凸函数，这里统一一下凸函数和凹函数。
我们主要看凸函数，不要顾名思义。。。先看看图片。
然后你会发现，这和学校里教的好像不一样？！？
原因就要涉及到东西方差异的问题了，这里采用 oi-wiki 的定义（当然图也是那上面的）。
\mathbf{R} 上的凸函数
如果函数 f: \mathbf{R} \rightarrow \mathbf{R} \cup \{ \pm \infty \}，对于所有 x, y \in \mathbf{R} 和 \alpha \in (0, 1) 都满足
就称函数 f 为凸函数，其中 \pm \infty 的运算法则规定为其乘以任何正实数或是加上任何实数都等于它本身，且对于任何实数 \mathbf{R} 都有 -\infty \lt x \lt \infty。
同理，凹函数就是把 \leq 改成 \geq。
离散点集上的凸函数
函数 f:\mathbf{Z} \rightarrow \mathbf{R} \cup \{\pm \infty\} 是凸的，当且仅当
对于所有 x \in \mathbf{Z} 成立。
我们举几个凸函数的例子：
- 常数函数，如 f(x) = 1；
- 一次函数，如 f(x) = kx + b；
- 绝对值函数，如 f(x) = |x|；
- 任何凸函数限制在某个区间上的结果。
方便起见，以下内容只使用凸函数进行讲解。
如果还想了解更多凸函数相关知识的话可以点这里，在此不再过多赘述。
Slope Trick
Slope Trick 是一种优化二维 DP 的方法，其原理就是维护凸函数上的一些信息，用数据结构进行快速转移，从而降低时间复杂度。
值得一提的是，这个不是斜率优化，这是两个东西，硬翻的话应该叫斜率技巧。
使用该算法优化的前提：
- DP 数组是二维的且第二维是连续的；
- 是分段一次函数；
- 是凸函数（凹函数也可以）；
- 一次函数的斜率为整数。
这样我们就可以将凸函数里斜率变化的位置，即拐点用数据结构来维护，如果斜率变化为 1 就加一次，大于 1 就加多次；
同时记录该凸函数最左边或最右边分段的一次函数，我们就可以确定一个凸函数。
如图，有这个函数：
可以选择维护最右边的函数信息 k = 2, b = -9 和拐点集合 \{3, 5, 5\}，其中为了区分斜率的变化我们在集合中加入了两次 5，这样就能表示这个函数了（之后默认维护右边的函数）。
同时，分段一次函数有两个优秀的性质：
- 两个凸函数相加还是凸函数。
设凸函数 f(x) 和 g(x)，其拐点集合为 L_f 和 L_g，其最右端的函数为 R_f(x) 和 R_g(x)，则 h(i) = f(x) + g(x) 为凸函数，同时我们合并点集和一次函数，即 L_h = L_f \cup L_g 和 R_h(x) = R_f(x) + R_g(x)。 - 凸函数加一次函数还是凸函数。
主包主包，这不是还在讲凸函数的问题吗？
别急啊，我们通过一道板子题正式了解 Slope Trick。
模板题：P4597 序列 sequence
给定一个序列，每次操作可以把某个数 +1 或 −1。要求把序列变成非降数列，求最少的操作次数。
1 \leq n \leq 5 \times 10 ^ 5，|a_i| \leq 10^9。
首先考虑朴素 DP，设 f_{i, j} 表示到第 i 个数时，将其变成 j 所需的最少操作次数。容易得出这样的转移方程式：
时间复杂度为 O(n \max a_i)，坠机警告。
也许你想到可以用 Slope Trick 优化，这样的话就需要证明这个 f 数组是一个凸函数或凹函数，即对于每个 i，f_{i, j} 是关于 j 的一个凸函数。
证明
首先 i = 1 时有 f_{1, j} = |a_1 - j|，为一个绝对值函数，顶点为 a_1，显然符合条件。
接下来考虑 f_{i - 1} \rightarrow f_{i} 是如何变化的。
观察转移式，我们发现 \min\limits_{k \leq j} f_{i - 1, k} 和 |a_i - j| 的值没有关系，不妨设 g_i(j) = \min\limits_{k \leq j} f_{i, k}，h_i(j) = |a_i - j|。则有：
已知凸函数加凸函数还是凸函数，因此如果 g_i(j) 和 h_i(j) 都是凸函数，自然说明 f_{i, j} 是凸函数。
显然 h_i(j) 是一个绝对值函数，现在只需要考虑 g_i(j)。
已知 f_1 是一个凸函数，且 g_{i - 1}(j) 表示 f_{i - 1, j} 的前缀 \min，所以 g_{i - 1}(j) 应该是一个分段函数斜率小于 1 的凸函数，大致图像如下：
因此 f 是个凸函数，然后就可以用 Slope Trick 优化了。
由于凸函数的斜率一定是递增的，我们规定斜率增加的都是 1，如果斜率一次增加了更多的话，就认为在转折点有相应的长度为 0 的线段。
于是设 d_i 表示 f_i 上斜率为 0 的线段的左端点（同时也是斜率为 -1 的线段的右端点），即最低点。
题目中要求的是求出最小代价，即 f_{n, d_n}，当然这个 d_n 是多少不需要考虑，因为我们只需要最小代价。
同时注意到整个转移其实是凸函数相加再前缀取 \min，且 g_{i - 1}(j) 后面的斜率始终为 0。
也就是说，大于 d_n 的部分我们都不需要维护，因为怎么变都不会影响最终答案。
因此只需要维护斜率小于 0 的部分即可。
考虑维护斜率小于 0 的线段，由于上面提到的斜率变化特点，我们选择大根堆（大根堆 q）来维护每条线段右边的拐点，一条线段的斜率就是完全弹出一个元素需要的次数的相反数。
例如，\{3, 2, 2, 1, 1, 1\} 中右端点（横坐标）为 3 的线段斜率是 -1，右端点为 2 的线段斜率为 -3，右端点为 1 的线段斜率为 -6。
神奇的是，这恰好满足之前提到的：
凸函数的斜率一定是递增的，我们规定斜率增加的都是 1，如果斜率一次增加了更多的话，就认为在转折点有相应的长度为 0 的线段。
现在我们知道了维护原理，但是想要求解出答案光知道斜率是不行的，我们需要知道每一个 a_i 对答案产生的影响。
也就是说我们需要知道当 a_i 加入之后，大根堆里原有的线段会发生什么变化。所以这里放一下规则（原出处）：
- 线段单降，在 a_i 左侧：
此时有 \min\limits_{k \leq j} f_{i - 1, k} = f_{i - 1, j}，所以 f_{i, j} = f_{i - 1, j} + a_i - j，可以发现斜率 -1。 - 线段单降，在 a_i 右侧：
\min\limits_{k \leq j} f_{i - 1, k} = f_{i - 1, j}，有 f_{i, j} = f_{i - 1, j} + j - a_i，斜率 +1。 - 线段单增，在 a_i 左侧:
找到此时单降的最后一个点 pos，\min\limits_{k \leq j} f_{i - 1, k} = pos，即 f_{i, j} = pos + a_i - j，斜率变为 -1。 - 线段单增，在 a_i 右侧：
\min\limits_{k \leq j} f_{i - 1, k} = pos，即 f_{i, j} = pos + j - a_i，斜率变为 1。
设答案 ans，即考虑 f_{i - 1} \rightarrow f_i 时 ans 如何变。
第一种情况：a_i \geq d_{i - 1}
我们发现 a_i 前面的线段斜率都 \lt 0，d_{i - 1} 又是 f_{i - 1, j} 中值最小时取到的 j，且有 d_{i - 1} \lt a_i，从而 a_i 可以用 d_{i - 1} 转移过来：f_{i, a_i} = f_{i - 1, d_{i - 1}} + a_i - a_i = f_{i - 1, d_{i - 1}}，所以 ans 保持不变。
考虑线段斜率的变化，这显然是符合变化规则一，那么所有线段的斜率都要减一，所以我们把 a_i 放入大根堆，这样其他所有元素完全弹出的次数加一，表示斜率减一。
第二种情况：a_i \lt d_{i - 1}
首先考虑答案如何变化。根据上面的变化规则我们发现 d_i 与 d_{i - 1} 的斜率变成了 0，所以 f_{i, d_i} = f_{i, d_{i - 1}} = f_{i - 1, d_{i - 1}} + d_{i - 1} - a_i，即 ans = ans + d_{i - 1} - a_i。
接下来是斜率变化。因为 d_{i - 1} 不再是最后单降的点，我们需要将其从堆中弹出，同时我们发现 a_i 两侧的线段斜率差值为 2，所以我们需要多放入一次 a_i 保证我们维护的斜率是正确的。
最后我们还需要求出 d_i 的值，我们发现大根堆的堆顶元素就是最后一个单降的点（即 d_i），只需取出堆顶并计算即可。
以上就是 Slope Trick 优化，时间复杂度降至 O(n \log n)，可以通过本题。
然后我们就能愉快的解决这道紫题啦！
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, ans;
priority_queue<int> q;
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
q.push(x);
if (!q.empty() && q.top() > x) ans += q.top() - x, q.pop(), q.push(x);
}
cout << ans << "\n";
return 0;
}
一些例题讲解
咕咕咕咕咕咕~
尾声
个人认为还是很难的，看下面的参考文章也能看出来。
主包也是前前后后折腾了 3 天才彻底搞懂。
看在主包这么努力的份上，点个赞再走吧~