题解 CF1406D【Three Sequences】

看错题了，我很生气。

problem

You are given a sequence of $ n $ integers $ a_1, a_2, \ldots, a_n $ .

You have to construct two sequences of integers $ b $ and $ c $ with length $ n $ that satisfy:

• for every $ i $ ( $ 1\leq i\leq n $ ) $ b_i+c_i=a_i $
• $ b $ is non-decreasing, which means that for every $ 1<i\leq n $ , $ b_i\geq b_{i-1} $ must hold
• $ c $ is non-increasing, which means that for every $ 1<i\leq n $ , $ c_i\leq c_{i-1} $ must hold

You have to minimize $ \max(b_i,c_i) $ . In other words, you have to minimize the maximum number in sequences $ b $ and $ c $ .

Also there will be $ q $ changes, the $ i $ -th change is described by three integers $ l,r,x $ . You should add $ x $ to $ a_l,a_{l+1}, \ldots, a_r $ .

You have to find the minimum possible value of $ \max(b_i,c_i) $ for the initial sequence and for sequence after each change.

\(n,q\leq 10^5\)。

solution

最小化 \(\max(b_1,c_n)\)。

首先考虑：如果 \(b-1\) 同时 \(c+1\)，那还不如不变。这也就是说，从 \(i\to i+1\) 调整 \(b,c\) 的时候，一定只有其中一个在变。
具体一点，考虑差分 \(a\)：\(d_i=a_i-a_{i-1}\)，那么如果 \(d_i>0\) 就给 \(c\)，否则给 \(b\)。

设 \(b_1=x\)。则 \(c_1=a_1-x\)，\(c_n=c_1+\text{所有正的} d_i\)，由于 \(d_i\) 现在固定，我们设 \(K=a_1+\sum_{i}[d_i>0]d_i\)。
则题目是最小化 \(\max(x,K-x)\)。使得 \(x=K-x\) 时原式最小，所以得到了 \(x=K/2\)（有一些上下取整问题，自己枚举一下）。

观察到区间加在差分序列上很容易维护，\(K\) 也很容易维护，于是做完了。