题解：AT_abc483_d [ABC483D] Glitchy Robot

__xiaoY · 2026-11-10 20:17:27 · 题解

观察题目，发现至多翻转一个，考虑枚举翻转了哪一位。

当翻转了 A_i 时，对于 i-1 及之前的移动没有影响，对于 i 及之后的移动产生了反方向 2\times A_i 的贡献。那么我们可以先统计前后缀最值，然后在每一位计算一次贡献更新答案。

具体来说，设 l 为左侧最大可达，r 为右侧最大可达，则 l=\min(\text{preMin}_{i-1},\text{sufMin}_i-2\times A_i)，r=\max(\text{preMax}_{i-1},\text{sufMax}_i-2\times A_i)，可达范围是 r-l+1。

:::success[AC code]

#include<bits/stdc++.h>
//__xiaoY
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
int a[200005];
ll sum[200005],ans;
ll pmn[200005],pmx[200005];
ll smn[200005],smx[200005];
signed main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i],sum[i]=sum[i-1]+a[i];
    smn[n+1]=2e18;
    smx[n+1]=-2e18;
    for(int i=1;i<=n;i++)
    {
        pmn[i]=min(pmn[i-1],sum[i]);
        pmx[i]=max(pmx[i-1],sum[i]);
    }
    for(int i=n;i>=1;i--)
    {
        smn[i]=min(smn[i+1],sum[i]);
        smx[i]=max(smx[i+1],sum[i]);
    }
    ans=pmx[n]-pmn[n]+1;
    for(int i=1;i<=n;i++)
    {
        ll ch=-a[i]*2;
        ll lsz=min(pmn[i-1],smn[i]+ch);
        ll rsz=max(pmx[i-1],smx[i]+ch);
        ans=max(ans,rsz-lsz+1);
    }
    cout<<ans;
    return 0;
}

:::