题目链接
题目解法
感觉是一个融合了许多技巧的题，很巧妙
题目要求 \(\max(h_i,h_{i+1},h_{i+2})-\min(h_i,h_{i+1},h_{i+2})=w_i\)，这可以转化成另一个只和两项有关的形式为：\(\max(|h_i-h_{i+1}|,|h_i-h_{i+2}|,|h_{i+1}-h_{i+2}|)=w_i\)
令 \(d_i=h_{i+1}-h_i\)，所以限制为 \(\max(|d_i|,|d_{i+1}|,|d_i+d_{i+1}|)=w_i\)
这是这道题的第一个巧妙之处：转成差分序列
考虑一个朴素的 \(dp\) 做法，令 \(f_{i,j}\) 为 \(|d_i|=j\)，且满足前 \(i-1\) 个限制是否可行（注意，这里是 \(|b_i|\)）
转移比较简单：
- \(f_{i,j}\to f_{i+1,w_i}(0\le j\le w_i)\)
- \(f_{i,w_i}\to f_{i+1,j}(0\le j\le w_i)\)
- \(f_{i,j}\to f_{i+1,w_i-j}(0\le j\le w_i)\)
为什么前 2 种情况不需要考虑 \(|d_i+d_{i+1}|\) 会不会 \(>w_i\)，因为 \(d_i\le w_i,\;d_{i+1}\le w_i\)，那么一定可以通过后面的调整符号从而使 \(d_i+d_{i+1}\le w_i\)
接下来是这道题的第二个巧妙之处：在 1 的形态上进行考虑
考虑 \(f\) 值为 1 的连续段的变化，可以发现，2 操作会使所有区间合并成 \([0,w_i]\)，操作 1 会增加一个单点，操作 3 只是按照 \(\frac{w_i}{2}\) 翻转，不会改变单点和区间个数
所以，可以得到一个局面下，1 的连续段为至多一个区间和 \(O(n)\) 个单点
考虑维护区间和单点的变化
操作 1 和 2 是好维护的
操作 3 需要按照 \(\frac{w_i}{2}\) 翻转，手玩一下发现一个神奇的结论是：按照 \(\frac{w_i}{2}\) 翻转 等价于 按照 \(0\) 翻转，然后再往右平移 \(w_i\)，这里是第三个巧妙之处
这样就好维护了，只需要记录当前是正的还是反的，以及平移的距离
这样可判断 YES OR NO
考虑构造方案
可以得到一个贪心的想法是，\(d_{n-1}\) 随便一个 1 位置，从后往前构造 \(d_i\)
如果 \(d_{i+1}=w_i\)，则 \(d_i\) 为随便一个可行的位置，如果 \(d_i\) 可以为 \(w_i\)，则 \(d_i=w_i\)，否则 \(d_i=w_i-d_{i+1}\)
但这样只确定了 \(|d_i|\)，我们需要定正负性，这个从后往前，如果我们不需要 \(|d_i+d_{i+1}|=w_i\)，那么就使 \(d_i\) 和 \(d_{i+1}\) 异号
时间复杂度 \(O(n\log n)\)
#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
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 &FF){
FF=0;int RR=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
FF*=RR;
}
const int N=1000100;
const LL inf=1e18;
int n;
LL C,w[N],d[N],ps[N],ans[N];
set<LL> single;
int main(){
read(n),read(C);
F(i,1,n-2) read(w[i]);
//按w_i/2翻转 等价于 按原点翻转，在往右平移a_i
LL l=0,r=C,tag2=0;//翻转之后需要平移的距离
bool tag1=0;//是否需要以原点为中心翻转
F(i,1,n-2){
LL le,ri,ed;
if(tag1) le=-w[i]+tag2,ri=tag2,ed=-w[i]+tag2;
else le=-tag2,ri=w[i]-tag2,ed=w[i]-tag2;
chkmax(l,le),chkmin(r,ri);
while(!single.empty()&&(*single.begin())<le) single.erase(*single.begin());
while(!single.empty()&&(*single.rbegin())>ri) single.erase(*single.rbegin());
if(l>r&&single.empty()){ puts("NO");exit(0);}
if((l<=ed&&ed<=r)||single.find(ed)!=single.end()){//f[i-1][w_i]=1
single.clear(),tag1=0,tag2=0;
l=0,r=w[i],ps[i]=w[i];continue;
}
//find one possible sol
if(l<=r){
if(tag1) ps[i]=-l+tag2;
else ps[i]=l+tag2;
}
else{
if(tag1) ps[i]=-(*single.begin())+tag2;
else ps[i]=(*single.begin())+tag2;
}
tag1^=1,tag2=w[i]-tag2;
if(tag1) single.insert(tag2-w[i]);
else single.insert(w[i]-tag2);
}
puts("YES");
if(l<=r) d[n-1]=tag1*(-1)*l+tag2;
else d[n-1]=tag1*(-1)*(*single.begin())+tag2;
// F(i,1,n-2) cout<<ps[i]<<' ';cout<<'\n';
DF(i,n-2,1){
if(w[i]==d[i+1]) d[i]=ps[i];
else if(w[i]==ps[i]) d[i]=w[i];
else d[i]=w[i]-d[i+1];
}
// F(i,1,n-1) cout<<d[i]<<' ';cout<<'\n';
int neg=1;
DF(i,n-2,1){
if(abs(d[i])+abs(d[i+1])!=w[i]) neg*=-1;
d[i]*=neg;
}
// F(i,1,n-1) cout<<d[i]<<' ';cout<<'\n';
// F(i,1,n-2) assert(max(abs(d[i]),max(abs(d[i+1]),abs(d[i]+d[i+1])))==w[i]);
ans[1]=0;
F(i,1,n-1) ans[i+1]=ans[i]+d[i];
LL mn=inf;
F(i,1,n) chkmin(mn,ans[i]);
F(i,1,n) ans[i]-=mn;
F(i,1,n) printf("%lld ",ans[i]);puts("");
fprintf(stderr,"%d ms\n",int(1e3*clock()/CLOCKS_PER_SEC));
return 0;
}