题解：AT_ndpc2026_g 口

manboo · 2026-05-07 11:58:51 · 题解

题意概述：

给你长度为 n 的数组 A，进行 q 次操作，每次给定 i,v，将 A_i 修改为 v。每次操作后，求以下值：

令长度为 n 的数组 B 初值全部为 0，选择一个位置 x\left(1\le x\le n\right)，进行若干次移动，每次可以移动到 x+1,x,x-1 但不能移动到 0 或 n+1，移动后的位置为 y，将 B_y 加 1。求 \sum\limits_{i=1}^{n}\left|A_i-B_i\right| 的最小值。

感觉这个 B 数组有点冗余，考虑将题面转换，将“增加 B 数组的值”改为“减少 A 数组的值”，求 \sum\limits_{i=1}^{n}\left|A_i\right| 的最小值。

不难发现几个结论：

• 从某一点 x 出发，一直向一个方向走，到 y 结束，一定比从 x,y 中间的某一点 z 出发，先到 x，再折返回去到 y 要不劣。

• 当你到达一个正整数时，一定要一直停留在这里，将其变为 0，然后选择继续走或结束。

• 当你处于一段连续的正整数的一端时，一定要将这一段正整数全部变为 0，到达另一端，然后选择继续走或结束。

• 当你下一步会到达 0 时，要么不走（结束），要么走，会让它减成 -1，然后一定不会停留在这里，必须继续走，把这段连续的 0 全部减成 -1，并到达下一个正整数，然后执行上一步。

因此，必然是选择某段连续的正整数的一端，将这一段正整数全部变为 0，到达另一端后，要么选择结束，要么将接下来一段连续的 0 全部减成 -1，并将再下面一段连续正整数全部变为 0。初始答案为 \sum\limits_{i=1}^{n}A_i，那么这两段就会使答案加上这一段 0 的个数，减去这一段正整数之和。

如果令所有的 0 初值都为 -1 的话，那么问题竟然转变为了——带修最大子段和！

用线段树实现单点修改，区间查询最大子段和，也是非常板了。

还是考虑初始答案为 ans=\sum\limits_{i=1}^{n}A_i，那么每次修改后的答案即为 ans 减去最大子段和。

上代码：

typedef long long ll;
const int N=1e5+10;
int n,q,a[N];
ll sum;
struct node
{
    ll sum,maxl,maxr,ans;
}o[N*4];
node pushup(node l,node r)
{
    node ret;
    ret.sum=l.sum+r.sum;
    ret.maxl=max(l.maxl,l.sum+r.maxl);
    ret.maxr=max(r.maxr,r.sum+l.maxr);
    ret.ans=max({l.ans,r.ans,l.maxr+r.maxl});
    return ret;
}
void build(int x,int l,int r)
{
    if(l==r)
    {
        o[x]=node{a[l],max(0ll,a[l]),max(0ll,a[l]),max(0ll,a[l])};  //注意！单点最大子段和至少为0，因为可以不操作 
        return ;
    }
    int mid=(l+r)>>1;
    build(x<<1,l,mid);
    build(x<<1|1,mid+1,r);
    o[x]=pushup(o[x<<1],o[x<<1|1]);
}
void change(int x,int l,int r,int t,int v)
{
    if(l==r)
    {
        o[x]=node{v,max(0ll,v),max(0ll,v),max(0ll,v)};
        return ;
    }
    int mid=(l+r)>>1;
    if(t<=mid) change(x<<1,l,mid,t,v);
    if(t>=mid+1) change(x<<1|1,mid+1,r,t,v);
    o[x]=pushup(o[x<<1],o[x<<1|1]);
}
int main()
{
    n=read(),q=read();
    for(int i=1;i<=n;i++)
    {
        a[i]=read(),sum+=a[i];
        if(!a[i]) a[i]=-1;
    }
    build(1,1,n);
    for(int i=1;i<=n;i++) if(a[i]==-1) a[i]=0;
    for(int i=1,x=0,y=0;i<=q;i++)
    {
        x=read(),y=read();
        sum-=a[x],sum+=y,a[x]=y;
        if(!y) y=-1;
        change(1,1,n,x,y);
        print(sum-o[1].ans),putchar('\n');
    }
    return 0;
}