codeforces-#670-D

codeforces-#670-D

九月 18, 2020

D. Three Sequences

题意

给出一个长度为n<1e5的数组a

要求构造出两个数组b和c，使得满足以下条件：

  • b数组非减
  • c数组非增
  • bi+ci=ai

多组询问

每次将数组a的区间[L,R]的数+x

问能构造出两个数组中最大的数max(c1,bn)最小是多少

题解

根据如下方式贪心构造数组c和b：

  • b数组非减

    那么$a_i>a_{i-1}$时令$c_i=c_{i+1}$

    则有 $b_i>b_{i-1}$

  • c数组非增

    那么$a_i<a_{i-1}$时令$b_i=b_{i+1}$

    则有 $c_i<c_{i-1}$

求b1到bn的增量为$sum=∑_{i=2}^n max(0,a_i−a_{i−1}) $

于是对于$b_1=a_1-c_1,b_n=b_1+sum$

那么有$max(c_1,b_n)=max(c_1,a_1-c_1+sum)$

为了让最大值最小 $c_1=(a_1-sum)/2$

对于每次询问将a的区间[L,R]的数+x

考虑到我们求得答案所需要的量

实际上只会改变$a_L-a_{L-1},a_{R+1}-a_R$ 以及a1(可能会被改变)

所以每次询问更新a1和sum就能O1求出解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define Turnoff std::ios::sync_with_stdio(false)
const ll Max=1e5+5;
const ll Mod=998857459;
/*

*/
ll data[Max],de[Max];
int main() {
    //Turnoff;
    int n;cin>>n;
    ll sum=0;
    for(int i=0;i<n;i++)cin>>data[i];
    for(int i=1;i<n;i++)de[i]=data[i]-data[i-1],sum+=max(0ll,de[i]);
    ll c1=(data[0]+sum)/2;
    cout<<max(c1,data[0]+sum-c1)<<endl;
    int q;cin>>q;
    while(q--){
        ll L,R,add;cin>>L>>R>>add;L--;
        if(L>0&&L<n)sum-=max(0ll,de[L]);
        if(R>0&&R<n)sum-=max(0ll,de[R]);
        if(L==0||R-1==0)data[L]+=add;
        de[L]+=add;de[R]-=add;
        if(L>0&&L<n)sum+=max(0ll,de[L]);
        if(R>0&&R<n)sum+=max(0ll,de[R]);
        ll c1=(data[0]+sum)/2;
        cout<<max(c1,data[0]+sum-c1)<<endl;
    }
}