CF1406D-Three Sequences

题意

给出一个序列 (a_1,a_2,a_3,dots ,a_n)，需要构造两个序列 (b) 和 (c) ，并且满足下列要求：

• (b_i+c_i=a_i (1leq i leq n))
• (1<i leq n,b_igeq b_{i-1})
• (1<i leq n,c_ileq c_{i-1})

现在需要最小化序列 (b) 和 (c) 的最大值，同时会有 (q) 次修改，每次给 ([l,r]) 区间上的数都加上 (x)，输出没有修改和修改后的答案。

(1leq n leq 10^5,-10^9leq a_i leq 10^9,1leq q leq 10^5,-10^9leq x leq 10^9)

题目链接：https://codeforces.com/contest/1406/problem/D

分析

要使得 (b) 和 (c) 序列中的最大值最小，实际就是要最小化：(max(c_1,b_n))。

• 当 (a_i>a_{i-1}) 时，贪心可得：(b_i=b_{i-1}+a_i-a_{i-1},c_i=c_{i-1})；
• 当 (a_i<a_{i-1}) 时，同理：(b_i=b_{i-1},c_i=c_{i-1}+a_i-a_{i-1})；

可令 (S=sum_{i=2}^{n}{max(0,a_i-a_{i-1})})，那么 (b_n=b_1+S)。即最终要最小化：(max(c_1,a_1-c_1+S))，易得，当 (c_1=frac{S+a_1}{2}) 时，有最小值 (max(frac{S+a_1}{2},S+a_1-frac{S+a_1}{2}))。

当进行区间修改时，对于差分数组而言，只有 (a_l-a_{l-1}) 和 (a_{r+1}-a_r) 会改变。

复杂度：(O(n+q))

代码

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N=1e5+5;
ll d[N];
int main()
{
    int n,q,a=0,b=0;
    ll c;//小心爆int
    scanf("%d",&n);
    ll sum=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a);
        d[i]=a-b;
        if(i==1) c=a;
        if(i>1) sum+=max(d[i],0LL);
        b=a;
    }
    scanf("%d",&q);
    ll ans=(c+sum)/2;
    ans=max(ans,sum+c-ans);
    while(q--)
    {
        printf("%lld
",ans);
        int l,r,x;
        scanf("%d%d%d",&l,&r,&x);
        if(l>1)
        {
            sum=sum-max(0LL,d[l])+max(0LL,d[l]+x);
            d[l]+=x;
        }
        if(r<n)
        {
            sum=sum-max(0LL,d[r+1])+max(0LL,d[r+1]-x);
            d[r+1]-=x;
        }
        if(l<=1&&1<=r) c+=x;
        ans=(sum+c)/2;
        ans=max(ans,sum+c-ans);
    }
    printf("%lld
",ans);
    return 0;
}