CF 1406-D

D. Three Sequences

• 题意：给一个长度为 $n$ 的数组 $a$ ，构造两个相同长度的数组 $b$，$c$ 。
  要求：$b[i]+c[i]=a[i]$，并且数组 $b$ 单调不减，数组 $c$ 单调不增。让我们最小化$max(b[n],c[1])$，并且输出。
  除了初始数组，会有 $q$ 次区间加操作，对于每次更新完的数组 $a$，同样要输出$max(b[n],c[1])$的最小值。

• 思路：$b[i]+c[i]=a[i]$，$b[i?1]+c[i?1]=a[i?1]$ $?$ $b[i]?b[i?1]+c[i]?c[i?1]=a[i]?a[i?1]$
  因为数组 $b$ 单调不减，所以当 $a[i]?a[i?1]>=0$ 时，令 $c[i]=c[i?1]$ 且 $b[i]=b[i?1]+a[i]?a[i?1]$
  因为数组 $c$ 单调不增，所以当 $a[i]?a[i?1]<0$ 时，令 $b[i]=b[i?1]$ 且 $c[i]=c[i?1]+a[i]?a[i?1]$

所以假设 $c[1]=x$，那么 $b[1]=a[1]?x$。
$k=\sum _{i=2}^{n}max(0,a[i]?a[i?1])$
由上述的构造我们可以得到 $b[n]=b[1]+k=a[1]?x+k$
所以我们要最小化 $max(b[n],c[1])$ 也即最小化 $max(a[1]?x+k,x)$
显然，当 $a[1]?x+k==x$ 时，即 $x=\frac{a[1]+k}{2}$ 时，最大值最小。

关于区间加的操作，这里因为只关心 $k$ 值的变化和 $a[1]$ 值的变化，所以开一个数组$dif[i]=a[i]?a[i?1]$, 我们利用差分的思想，区间 $[l,r]$ 操作只更新差值 $dif[l]$ 和 $dif[r+1]$即可。
但是需要注意的是 $dif[1]$ 影响 $a[1]$ 的更新，而 $dif[1]$ 和 $dif[n+1]$ 都不影响 $k$ 的更新。

然后 $O(n+q)$ 即可解决。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#define INF 0x3f3f3f3f
#define lowbit(x) x & (-x)
using namespace std;
typedef long long ll;
const int maxN = 100005;
ll read() {
    ll x = 0, f = 1; char ch = getchar();while(ch < '0' || ch > '9') {
     if(ch == '-') f = -f; ch = getchar(); }while(ch >= '0' && ch <= '9') {
     x = x * 10 + ch - '0'; ch = getchar(); }return x * f;
}
ll n, a[maxN]; //n->数组长度[1, n]
ll dif[maxN], k;
void solve(){
    a[1] += dif[1], dif[1] = 0;ll c1 = (a[1] + k) >> 1;ll bn = a[1] - c1 + k;cout << max(c1, bn) << endl;
}
void update(int pos, ll &x, ll val) {
    if(pos > n) return;if(x > 0) {
    k -= x;}x += val;if(pos <= 1) return;if(x > 0) {
    k += x;}
}
int main()
{
    n = read();for(int i = 1; i <= n; ++ i ) {
    a[i] = read();dif[i] = a[i] - a[i - 1];}dif[1] = 0;k = 0;for(int i = 2; i <= n; ++ i ) {
    k += dif[i] > 0 ? dif[i] : 0;}solve();ll q; q = read();while(q -- ) {
    int l, r; ll val;cin >> l >> r;val = read();update(l, dif[l], val);update(r + 1, dif[r + 1], -val);solve();}return 0;
}