题解：AT_abc483_d [ABC483D] Glitchy Robot

· · 题解

题解：AT_abc483_d [ABC483D] Glitchy Robot

思路

设 pre 为 a 的前缀和数组，pre_0=0。发现机器人移动的区间是 \min_{i=0}^{n}pre_i 到 \max_{i=0}^{n}pre_i，答案为 \max_{i=0}^{n}pre_i-\min_{i=0}^{n}pre_i+1。接下来我们考虑改一个数对 pre 的影响。假设我们改的数是 a_i，则 pre 的第 i 位到第 n 位都会减去 2a_i。所以我们考虑枚举要改哪一个数，用线段树维护 pre 的变化和最大值和最小值。最后取个 \max 即可。

AC Code

#include<bits/stdc++.h>
using namespace std;
#define int long long 
int n,a[200005],pre[200005];
struct node{
    int l,r,maxn,minn;
    int lz;
}sgt[4*1000000+5];
inline void pushup(int k){
    sgt[k].maxn=max(sgt[k<<1].maxn,sgt[k<<1|1].maxn);
     sgt[k].minn=min(sgt[k<<1].minn,sgt[k<<1|1].minn);
}
inline void pushdown(int k){
    if(sgt[k].lz){
        sgt[k<<1].maxn+=sgt[k].lz;
        sgt[k<<1].minn+=sgt[k].lz;
        sgt[k<<1|1].maxn+=sgt[k].lz;
        sgt[k<<1|1].minn+=sgt[k].lz;
        sgt[k<<1].lz+=sgt[k].lz;
        sgt[k<<1|1].lz+=sgt[k].lz;
        sgt[k].lz=0;
    }
    return;
}
void build(int n,int l,int r){
    sgt[n].l=l,sgt[n].r=r;
    if(l==r){
        sgt[n]=(node){l,r,pre[l],pre[l],0};
        return;
    }
    int mid=(l+r)>>1;
    build(n<<1,l,mid);
    build(n<<1|1,mid+1,r);
    pushup(n);
}
void add(int nw,int l,int r,int x){
    if(l<=sgt[nw].l&&sgt[nw].r<=r){
        sgt[nw].maxn+=x;
        sgt[nw].minn+=x;
        sgt[nw].lz+=x;
        return;
    }
    pushdown(nw);
    int mid=(sgt[nw].l+sgt[nw].r)>>1;
    if(l<=mid)add(nw<<1,l,r,x);
    if(r>mid)add(nw<<1|1,l,r,x);
    pushup(nw);
}
int ask(int nw,int l,int r){
    if(sgt[nw].l>=l&&sgt[nw].r<=r)return sgt[nw].maxn;
    pushdown(nw);
    int mid=(sgt[nw].l+sgt[nw].r)>>1,ans=LLONG_MIN;
    if(l<=mid)ans=ask(nw<<1,l,r);
    if(r>mid)ans=max(ans,ask(nw<<1|1,l,r));
    return ans;
}
int ask2(int nw,int l,int r){
    if(sgt[nw].l>=l&&sgt[nw].r<=r)return sgt[nw].minn;
    pushdown(nw);
    int mid=(sgt[nw].l+sgt[nw].r)>>1,ans=LLONG_MAX;
    if(l<=mid)ans=ask2(nw<<1,l,r);
    if(r>mid)ans=min(ans,ask2(nw<<1|1,l,r));
    return ans;
}
int ans=0;
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){cin>>a[i];pre[i]=pre[i-1]+a[i];}
    build(1,0,n);
    ans=(ask(1,0,n)-ask2(1,0,n))+1;
    for(int i=1;i<=n;i++){
        add(1,i,n,-2*a[i]);
        int minn=ask2(1,0,n),maxn=ask(1,0,n);
        ans=max(ans,maxn-minn+1);
        add(1,i,n,2*a[i]);
    }
    cout<<ans;
    return 0;
}