题目大意
给出长度为 $n - 2$ 的数组 $w_i$，请你构造一个长度为 $n$ 的数组 $a$ 满足 $\forall i \in [1,~n - 2],~\max(a_i,~a_{i + 1},~a_{i + 2}) - \min(a_i,~a_{i + 1},~a_{i + 2}) = w_i$。若不能构造输出 NO。
$n \le 10^6,~0 \le w_i \le 10^{12},~0 \le a_i \le 10^{18}$
分析
考虑令 $c_i = a_{i + 1} - a_i$，则 $w_i = \max(|c_i|,~|c_{i + 1}|,~|c_i + c_{i + 1}|)$。
在确定 $c_i$ 考虑 $w_i$ 对 $c_{i + 1}$ 的限制时我们发现，我们可以通过将 $a_1 \sim a_{i + 1}$ 全部乘上 $-1$ 以使得 $c_1 \sim c_i$ 全都乘上 $-1$，容易发现这并不会影响 $w_1 \sim w_{i - 1}$ 带来的所有限制。因此我们发现我们在研究该限制时并不关心 $c_i$ 的符号，我们令 $d_i = |c_i|$，则 $w_i = \max(d_i,~d_{i + 1},~d_i + d_{i + 1})$。
考虑对该限制分别考虑最大值在哪一项上取到。设状态 $f_{i,~j}$ 表示考虑了 $d_1 \sim d_i$，且 $d_i = j$ 的方案是否合法。则对于所有合法情况 $f_{i,~j}$，有：
- 若 $j = w_i$，则 $\forall k \in [0,~w_i],~f_{i + 1,~k} = \text{True}$。
- 若 $0 < j \le w_i$，则 $f_{i + 1,~w_i} = \text{True}$。
- 若 $0 < j \le w_i$，$f_{i + 1,~w_i - j} = \text{True}$。
仔细观察，我们发现若 $f_{i,~w_i} = \text{True}$，$f_{i + 1}$ 数组中全部能取到的部分都为 $\text{True}$，不需要考虑其他两个情况；若 $f_{i}$ 数组中存在一项为 $\text{True}$ 那么 $f_{i + 1,~w_i}$ 为 $\text{True}$。这两种情况均可快速判断，而情况 3 则需要将所有合法状态 $j$ 转换为 $w_i - j$。
考虑维护 $f_i$ 数组中连续的 $\text{True}$ 段，则对于一个段 $[l,~r]$，其转移后为 $[w_i - r,~w_i - l]$。容易发现其由一个翻转操作和一个平移操作构成。因此每次从 $i$ 转移到 $i + 1$ 时，只需判断情况 1 和 2，然后再全局修改连续段的翻转和平移情况即可。若在转移到 $n - 1$ 前连续段集合为空，则无解，否则有解。
考虑如何构造 $d$ 数组。我们可以在最终的连续段集合中任取一个点的值作为 $d_{n - 1}$，考虑从后往前构造出整个 $d$ 数组，发现只有三种情况：
- 若 $d_i$ 可以等于 $w_i$，则令 $d_i = w_i$。因为若 $d_i = w_i$，则 $d_{i + 1}$ 可以取任意可以取到的值，所以这么做并不会影响正确性。
- 若 $d_{i + 1} = w_i$，则令 $d_i$ 为任意可以取到的小于 $w_i$ 的值。
- 若不满足上面的两个条件，则令 $d_i = w_i - d_{i + 1}$。
需要注意的是这里需要用到“任意可以取到的小于 $w_i$ 的值”，这需要实现中在转移 $f$ 时提前记录该项和 $d_i$ 能否取到 $w_i$ 值。
构造完 $d$ 数组后，考虑如何构造 $c$。这则相对简单，判断 $d_i + d_{i + 1}$ 是否等于 $w_i$。若不等于，则 $c_i$ 与 $c_{i + 1}$ 需异号，否则需同号。
最后根据 $c$ 数组随意构造出满足每个元素均为非负整数的 $a$ 数组即可。
代码
/**
* @file 1500F.cpp
* @author Macesuted (i@macesuted.moe)
* @date 2022-03-03
*
* @copyright Copyright (c) 2022
* @brief
* My Tutorial: https://macesuted.moe/article/cf1500f
*
*/
#include <bits/stdc++.h>
using namespace std;
namespace io {
#define SIZE (1 << 20)
char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55];
int f, qr;
inline void flush(void) { return fwrite(obuf, 1, oS - obuf, stdout), oS = obuf, void(); }
inline char getch(void) {
return (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS++)) : *iS++);
}
void putch(char x) {
*oS++ = x;
if (oS == oT) flush();
return;
}
string getstr(void) {
string s = "";
char c = getch();
while (c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == EOF) c = getch();
while (!(c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == EOF)) s.push_back(c), c = getch();
return s;
}
void putstr(string str, int begin = 0, int end = -1) {
if (end == -1) end = str.size();
for (int i = begin; i < end; i++) putch(str[i]);
return;
}
template <typename T>
T read() {
T x = 0;
for (f = 1, c = getch(); c < '0' || c > '9'; c = getch())
if (c == '-') f = -1;
for (x = 0; c <= '9' && c >= '0'; c = getch()) x = x * 10 + (c & 15);
return x * f;
}
template <typename T>
void write(const T& t) {
T x = t;
if (!x) putch('0');
if (x < 0) putch('-'), x = -x;
while (x) qu[++qr] = x % 10 + '0', x /= 10;
while (qr) putch(qu[qr--]);
return;
}
struct Flusher_ {
~Flusher_() { flush(); }
} io_flusher_;
} // namespace io
using io::getch;
using io::getstr;
using io::putch;
using io::putstr;
using io::read;
using io::write;
bool mem1;
#define maxn 1000005
typedef pair<long long, long long> pll;
long long a[maxn], d[maxn], w[maxn], v[maxn], limd[maxn];
set<pll> S;
void solve(void) {
int n = read<int>();
long long C = read<long long>();
for (int i = 1; i < n; i++) limd[i] = numeric_limits<long long>::max();
for (int i = 1; i <= n - 2; i++)
w[i] = read<long long>(), limd[i] = min(limd[i], w[i]), limd[i + 1] = min(limd[i + 1], w[i]);
S.emplace(0, limd[1]);
long long A = +1, B = 0;
for (int i = 1; i <= n - 1; i++) {
if (A == +1) {
while (!S.empty() && S.rbegin()->first + B > limd[i]) S.erase(--S.end());
if (!S.empty() && S.rbegin()->second + B > limd[i]) {
int l = S.rbegin()->first;
S.erase(--S.end()), S.emplace(l, limd[i] - B);
}
} else {
while (!S.empty() && -S.begin()->second + B > limd[i]) S.erase(S.begin());
if (!S.empty() && -S.begin()->second + B > limd[i]) {
int r = S.begin()->second;
S.erase(S.begin()), S.emplace(B - limd[i], r);
}
}
long long tw = (w[i] - B) / A;
auto p = S.lower_bound({tw + 1, tw + 1});
if (p != S.begin() && (--p)->second >= tw) {
v[i] = w[i];
S.clear(), S.emplace(0, limd[i + 1]), A = +1, B = 0;
continue;
}
if (S.empty()) return putstr("NO\n");
v[i] = S.begin()->first * A + B;
if (i == n - 1) break;
A = -A, B = w[i] - B;
tw = (w[i] - B) / A;
p = S.lower_bound({tw + 1, tw + 1});
if (p == S.begin() || (--p)->second < tw) S.emplace(tw, tw);
}
d[n - 1] = v[n - 1];
putstr("YES\n");
for (int i = n - 2; i; i--)
if (v[i] == w[i])
d[i] = w[i];
else if (d[i + 1] == w[i])
d[i] = v[i];
else
d[i] = abs(w[i] - d[i + 1]);
long long minVal = 0, pre = 0;
for (int i = 2, id = +1; i <= n - 1; i++) {
if (abs(d[i - 1]) + abs(d[i]) != w[i - 1]) id = -id;
d[i] *= id;
minVal = min(minVal, pre += d[i]);
}
a[1] = -minVal;
for (int i = 2; i <= n; i++) a[i] = a[i - 1] + d[i - 1];
for (int i = 1; i <= n; i++) write(a[i]), putch(" \n"[i == n]);
return;
}
bool mem2;
int main() {
#ifdef MACESUTED
cerr << "Memory: " << abs(&mem1 - &mem2) / 1024. / 1024. << "MB" << endl;
#endif
int _ = 1;
while (_--) solve();
#ifdef MACESUTED
cerr << "Time: " << clock() * 1000. / CLOCKS_PER_SEC << "ms" << endl;
#endif
return 0;
}
Comments | NOTHING