题解 SP1716 【GSS3 - Can you answer these queries III】

· · 题解

若 \LaTeX 炸了，可移步云剪切版或博客。

题解：

我们需要维护区间的最大子段和。

对于维护这种类型的数据，比较常用的就是线段树。

设区间 (l,r) 的最大子段和为 \operatorname{data}(l,r)。

我们称区间内达到最大子段和的子段为最大子段。

将区间 (l,r) 分成 (l,mid) \cup (mid+1,r)，那么区间 (l,r) 的最大子段是哪一段呢？

若为前两种，可将 \operatorname{data}L 与 \operatorname{data}R 加入候选值。

若为最后一种，我们需要左区间的后缀和与右区间的前缀和最大。不难发现，取到最大值时，必定是区间 L 的最大后缀和与区间 R 的最大前缀和之和。

设区间的最大前缀和 \operatorname{pre} 与区间的最大后缀和 \operatorname{suf}。

在这些表示下，我们就能维护最大子段和了

\operatorname{data}(l,r)=\max(\operatorname{suf}L+\operatorname{pre}R,\max(\operatorname{data}L,\operatorname{data}R))

但是我们还要维护 \operatorname{pre} 与 \operatorname{suf}。

对于区间 (l,r)，其最大前缀和可能是哪一段呢？

设区间和 \operatorname{sum}，那么

\operatorname{pre}(l,r)=\max(\operatorname{pre}L,\operatorname{sum}L+\operatorname{pre}R)

同理，对于区间 (l,r) 的最大后缀和，可能是

即

\operatorname{suf}(l,r)=\max(\operatorname{suf}R,\operatorname{sum}R+\operatorname{suf}L)

最后还剩一个 \operatorname{sum} 需要维护，即是线段树的常规操作了。

回顾一下我们的维护方式：

\begin{aligned} \operatorname{data}(l,r) & =\max(\operatorname{suf}L+\operatorname{pre}R,\max(\operatorname{data}L,\operatorname{data}R))\\ \operatorname{pre}(l,r) & =\max(\operatorname{pre}L,\operatorname{sum}L+\operatorname{pre}R)\\ \operatorname{suf}(l,r) & =\max(\operatorname{suf}R,\operatorname{sum}R+\operatorname{suf}L) \end{aligned}

于是可以用线段树 \Theta((n+q)\log n) 完成此题。

代码中用结构体写的线段树。详见代码。

#include<bits/stdc++.h>
using namespace std;
const int maxn=50000+233;
int n,q,a[maxn];
struct Seg{
    int l,r,sum; //区间左右端点，区间和
    int data,pre,suf; //最大子段和，最大前缀和，最大后缀和
}tree[maxn*4];
void pushup(int pos){ //RT的维护
    tree[pos].sum=tree[pos*2].sum+tree[pos*2+1].sum;
    tree[pos].data=max(tree[pos*2].data,tree[pos*2+1].data);
    tree[pos].data=max(tree[pos].data,tree[pos*2].suf+tree[pos*2+1].pre);
    tree[pos].pre=max(tree[pos*2].pre,tree[pos*2].sum+tree[pos*2+1].pre);
    tree[pos].suf=max(tree[pos*2+1].suf,tree[pos*2].suf+tree[pos*2+1].sum);
}
void biuld(int pos,int l,int r){ //标准建树
    if(l==r){
        tree[pos].l=tree[pos].r=l;
        tree[pos].data=tree[pos].pre=tree[pos].suf=tree[pos].sum=a[l];
        return;
    }
    int mid=(l+r)/2;
    biuld(pos*2,l,mid);
    biuld(pos*2+1,mid+1,r);
    tree[pos].l=tree[pos*2].l;
    tree[pos].r=tree[pos*2+1].r;
    pushup(pos);    
}
void update(int pos,int x,int y){ //标准upd
    if(tree[pos].l==tree[pos].r){
        tree[pos].data=tree[pos].pre=tree[pos].suf=tree[pos].sum=y;
        return;
    }
    int mid=(tree[pos].l+tree[pos].r)/2;
    if(x<=mid)update(pos*2,x,y);
    else update(pos*2+1,x,y);
    pushup(pos);
}
Seg query(int pos,int l,int r){
    if(l<=tree[pos].l&&tree[pos].r<=r)return tree[pos];
    int mid=(tree[pos].l+tree[pos].r)/2;
    if(l<=mid&&r>mid){ //将(l,r)拆分成(l,mid)U(mid+1,r)
        Seg resl=query(pos*2,l,r);
        Seg resr=query(pos*2+1,l,r);
        Seg res;
        res.sum=resl.sum+resr.sum;
        res.data=max(resl.data,resr.data);
        res.data=max(res.data,resl.suf+resr.pre);
        res.pre=max(resl.pre,resl.sum+resr.pre);
        res.suf=max(resr.suf,resr.sum+resl.suf);
        return res;
    }
    else{ //若(l,r)没有完全包含pos所在区间，直接递归
        if(l<=mid)return query(pos*2,l,r);
        if(r>mid)return query(pos*2+1,l,r);
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    biuld(1,1,n);
    cin>>q;
    for(int i=1;i<=q;i++){
        int opt,l,r;
        cin>>opt>>l>>r;
        if(opt)cout<<query(1,l,r).data<<endl;
        else update(1,l,r);
    }
    return 0;
}