大家可以猜猜看为什么有两个标题，因为这个原因本文就不设密码了，被 He_ren 的原题创到了。
吐槽一下，He_ren 甚至出原题还用脚造数据，虽然数据确实比较难造。不过那两个 \(O(n^2)\) 老哥好像都没最后将所有数调整成非负，遗憾 20。
有人场切 * 3500 却没过签到题，我不说是谁。
题目描述
给定正整数 \(n,C\) 和长度为 \(n-2\) 的序列 \(w(0\leq w_i\leq C)\)。
你需要构造一个长度为 \(n\) 的序列 \(h\)，满足：
-
对于任意整数 \(i\in[1,n-2]\) 有 \(\max\{h_i,h_{i+1},h_{i+2} \} -\min\{h_i,h_{i+1},h_{i+2} \}=w_i\)。
-
序列 \(h\) 中的任意元素 \(h_i\) 满足 \(0\leq h_i\leq 10^{18}\)。
有解输出 YES 之后输出任意一个满足要求的序列 \(h\)，无解输出 NO。
数据范围：\(3\leq n\leq10^6\)，\(0\leq C\leq10^{12}\)。
题解
这道题在中山集训时讲过，感谢 Kostlin 大师。
不过当时笔者鸽了啊啊啊啊啊啊，于是模拟赛赛时补题.jpg
首先考虑差分，令 \(f_i=h_{i+1}-h_i\)。于是限制就转化成了 \(\max\{0, h_i, h_{i+1}\} - \min\{0, h_i, h_{i+1}\} = w_i\)，显然等价于 \(\max\limits_{i,j\in \{0,h_i,h_{i+1}\}}\{i-j\} = w_i\)。考虑展开这 \(9\) 项，不难发现 \(\max\limits_{i,j\in \{0,h_i,h_{i+1}\}}\{i-j\} = \max\{|h_i|,|h_{i+1}|,|h_i+h_{i+1}|\}\)。
之后考虑一个 DP，\(f_{i,j}\) 表示第 \(i\) 个位置 \(|h_i|=j(j\ge 0)\)，值为 \(0/1\) 表示是否有解。这么设状态的一个重要原因是，我们观察到一个性质，在确定 \(\max\{|h_i|,|h_{i+1}|,|h_i+h_{i+1}|\}\)，我们只关心相邻两个数是否同号，以及它们的绝对值，并不关心它们具体谁正谁负，或者到底是同正还是同负，只需要 DP 完构造方案时判断一下。
我们发现只需要维护值为 \(1\) 的 DP 状态集合即可。我们具体分析一下我们的 DP 转移：
-
\(h_i\) 和 \(h_{i+1}\) 同号，则显然 \(\max\{|h_i|,|h_{i+1}|,|h_i+h_{i+1}|\}=|h_i+h_{i+1}|\)。相当于是 \(f_{i,j}\to f_{i+1,w_i-j}\)；
-
\(h_i\) 和 \(h_{i+1}\) 异号，则显然 \(\max\{|h_i|,|h_{i+1}|,|h_i+h_{i+1}|\}=\max\{|h_i|,|h_{i+1}|\}\)。分类讨论一下：
- \(j=w_i\)，则 \(f_{i+1,k}(0\le k\le w_i)\)；
- \(k=w_i\)，则若存在 \(j\)，满足 \(f_{i,j}\)，则 \(f_{i+1,w_i}=true\)。
我们发现新状态中，首先，情况 1 是很好维护的，我们只需要维护一个一次函数 \(ax+b\) 即可，并且这里 \(a\in \{-1,1\}\)。其次，情况 2.1 也是很好维护的，相当于当前状态变成全集。最后，我们考虑情况 2.2。这样的状态我们额外维护一下即可。因为，我们注意到这样的状态每次要么是当前最大，要么是当前最小（取决于 \(a\) 的正负），删除状态的时候需要弹出头或尾，所以我们考虑使用 deque 维护，@帅气yuyue（雾。
时间复杂度 \(O(n)\)。
代码
#include <bits/stdc++.h>
#define int long long
#define SZ(x) (int) x.size() - 1
#define all(x) x.begin(), x.end()
#define ms(x, y) memset(x, y, sizeof x)
#define F(i, x, y) for (int i = (x); i <= (y); i++)
#define DF(i, x, y) for (int i = (x); i >= (y); i--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template <typename T> void chkmax(T& x, T y) { x = max(x, y); }
template <typename T> void chkmin(T& x, T y) { x = min(x, y); }
template <typename T> void read(T &x) {
x = 0; int f = 1; char c = getchar();
for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
x *= f;
}
const int N = 1e6 + 10;
int n, C, a = 1, b, l = -1e18, r = 1e18, t[N], ans[N], s[N];
deque <int> q;
int calc1(int x) {
return (x - b) / a;
}
int calc2(int x) {
return a * x + b;
}
signed main() {
read(n); read(C);
F(i, 1, n - 2) {
int x; read(x); t[i] = x;
int cx = calc1(x);
int L = calc1(0), R = cx; if (L > R) swap(L, R);
chkmax(l, L); chkmin(r, R);
while (q.size() && q.front() < L) q.pop_front();
while (q.size() && q.back() > R) q.pop_back();
if (q.empty() && l > r) return puts("NO"), 0;
if ((l <= r && (l == cx || r == cx)) || (q.size() && (q.front() == cx || q.back() == cx))) {
ans[i] = x;
a = 1, b = 0;
l = 0, r = x;
q.clear();
} else {
ans[i] = calc2(l > r ? q.front() : l);
a *= -1, b = x - b;
if (a == 1) q.push_back(calc1(x));
else q.push_front(calc1(x));
}
} puts("YES");
ans[n - 1] = calc2(l > r ? q.front() : l);
DF(i, n - 2, 1) {
assert(abs(ans[i + 1]) <= t[i]);
if (ans[i] == t[i] || abs(ans[i + 1]) == t[i]) {
if (ans[i + 1] > 0) ans[i] *= -1;
} else {
ans[i] = t[i] - abs(ans[i + 1]);
if (ans[i + 1] < 0) ans[i] *= -1;
}
}
int mn = 0;
F(i, 2, n) s[i] = s[i - 1] + ans[i - 1], chkmin(mn, s[i]);
F(i, 1, n) cout << s[i] - mn << " ";
return 0;
}