题意

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

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

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

\(1\leq n \leq 10^5,-10^9\leq a_i \leq 10^9,1\leq q \leq 10^5,-10^9\leq 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\n",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\n",ans);
    return 0;
}

CF1406D-Three Sequences

原文：https://www.cnblogs.com/1024-xzx/p/13661709.html