Problem 链链链 chain
你有一个长度为 \(n\) 的链，编号为 \(i (1 ≤ i < n)\) 的边连接着结点 \(i\) 与 \(i + 1\) 。每个结点 \(i\) 上有一个整数 \(a_i\)。你需要做以下操作 \(n − 1\) 次：
• 选择一条还未被断开的边，设其连接了点 \(i\) 与 \(i + 1\) ，将其断开。
• 断边后，对于所有与 \(i\) 联通的点 \(j\) ，找到 \(a_j\) 的最大值，设其为 \(x\) 。对于所有与 \(i + 1\) 联通
的点 \(k\) ，找到 \(a_k\) 的最大值，设其为 \(y\) 。
• 此次操作的代价为 \(|x − y|\) 。
求做完 \(n − 1\) 次操作的代价之和的最小值。
Input
输入的第一行包含两个整数 \(c, t\) ，表示测试点编号与测试数据组数。对于样例，\(c\) 表示该样例与测试点 \(c\) 拥有相同的限制条件。
接下来，对于每组测试数据：
第一行包含一个整数 \(n\)，表示链的长度。
第二行包含 \(n\) 个整数，第 \(i\) 个整数表示 \(a_i\) 。
Output
输出一行一个整数表示对应的答案。
Note
对于所有测试数据，保证：\(1 ≤ t ≤ 5, 1 ≤ n ≤ 2 × 10^5, 1 ≤ a_i ≤ 10^9\) 。
分析
\(O(n\log n)\) 做法：
可以贪心地断开边，考虑优先断开全局最大值与次大值，对于二者中间的数优先和最大值断开。剩下两段递归地断开即可。用 \(ST\) 表维护区间最值，总复杂度 \(O(n\log n)\) 。
\(O(n)\) 线性做法：
%%%拜谢nkp
考虑在线，前面所有输入已经构造为最优解的情况下新加入的 \(a_i\) 对答案的贡献。分情况讨论：
•当 \(a_i>a_{i-1}\) 且 \(a_i\ge a_{max}\) 时，要总体贡献最小一定是让 \(a_i\) 与 \(a_{i-1}\) 断开时的贡献为 \(a_i\ - \ a_{max}\) ，并同时更新 \(a_{max}\) ；
•当 \(a_i>a_{i-1}\) 且 \(a_i<a_{max}\) 时，\(a_i\) 被包含在已构造最优贡献的值域中，一定存在一种调整构造的方法使新增的 \(a_i\) 贡献为 \(0\) ；
•当 \(a_i \le a_{i-1}\) 时，无论先前的 \(a_{min}\) 与 \(a_i\) 的关系如何， \(a_{min}\) 都已经被取整体最大值的操作覆盖而不会影响贡献，存在的最小贡献即 \(a_{i-1} \ -\ a_i\) ；
所以经过 \(n\) 次添加操作得到的就是最优贡献，时间复杂度达到非常优秀的 \(O(n)\) ；只需在输入同时记录 \(a_{i-1}\) 和更新 \(a_{max}\) ，空间复杂度仅为 \(O(1)\)。
惊为天人！nkp：其实复杂度瓶颈在输入
\(O(n)\) AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read() {
int otto = 0;
char a = getchar();
while(!isdigit(a)) a = getchar();
while(isdigit(a)) {
otto = (otto << 1) + (otto << 3) + (a ^ 48);
a = getchar();
}
return otto;
}
void solve() {
int n = read(); ll ans = 0;
int fst = read(), mx = fst, lst = fst;
for(int i = 2; i <= n; i++) {
int x = read();
if(x <= lst) ans += abs(x - lst);
else if(x >= mx) ans += x - mx, mx = x;
lst = x;
}
printf("%lld\n", ans);
}
int main() {
freopen("chain.in", "r", stdin);
freopen("chain.out", "w", stdout);
int c = read(), T = read();
while(T--) solve();
}