[题解]线段树模板：GSS1&GSS3&GSS5

原题链接：GSS1 GSS3 GSS5

这三道题都是维护区间最大子段和，属于线段树的模板题，同样的思路可以A掉三道，是三倍经验。

GSS1：不带修区间最大子段和

考虑GSS1：如何用线段树维护一个不带修改的区间最大子段和。不难发现只需要记录这个区间的最大子段和mcc、最大前缀和lm、最大后缀和rm以及一个用于辅助计算的区间总和sum即可。

如何合并？

显然，一个区间的最大子段和必然从左右子区间的最大子段和与左区间最大后缀和加上右区间最大前缀和的最大值中产生。这样描述可能不清楚，写成表达式即：
node[rt].mcc=max(max(node[ls].mcc,node[rs].mcc),node[ls].rm+node[rs].lm);
对最大前(后)缀的维护同理，要么是左(右)区间的最大前(后)缀，要么是左(右)区间总和再加上右(左)区间的最大前(后)缀。
node[rt].lm=max(node[ls].lm,node[ls].sum+node[rs].lm);
node[rt].rm=max(node[rs].rm,node[rs].sum+node[ls].rm);
区间和显然就是无脑加，表达式略。

本题完结。（无慈悲）

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
namespace SegmentTree{
    const int MAXN = (50000<<2)+7;
    struct Node{
        int sum,lm,rm,mcc;
    }node[MAXN];
    inline void push_up(int rt){
        int ls=rt<<1,rs=rt<<1|1;
        node[rt].sum=node[ls].sum+node[rs].sum;
        node[rt].lm=max(node[ls].lm,node[ls].sum+node[rs].lm);
        node[rt].rm=max(node[rs].rm,node[rs].sum+node[ls].rm);
        node[rt].mcc=max(node[ls].rm+node[rs].lm,max(node[ls].mcc,node[rs].mcc));
    }
    void build(int l,int r,int rt){
        if(l==r){
            scanf("%d",&node[rt].sum);
            node[rt].lm=node[rt].rm=node[rt].mcc=node[rt].sum;
            return;
        }
        int m=(l+r)>>1;
        build(l,m,rt<<1);
        build(m+1,r,rt<<1|1);
        push_up(rt);
    }
    Node* query(int L,int R,int l,int r,int rt){
        if(L<=l&&r<=R)return node+rt;
        int m=(l+r)>>1;
        if(L>m)return query(L,R,m+1,r,rt<<1|1);
        if(R<=m)return query(L,R,l,m,rt<<1);
        else{
            Node* left=query(L,R,l,m,rt<<1);
            Node* right=query(L,R,m+1,r,rt<<1|1);
            Node* ans=new Node;
            ans->sum=left->sum+right->sum;
            ans->mcc=max(left->rm+right->lm,max(left->mcc,right->mcc));
            ans->lm=max(left->lm,left->sum+right->lm);
            ans->rm=max(right->rm,right->sum+left->rm);
            return ans;
        }
    }
}
int main(){
    int n;
    scanf("%d",&n);
    SegmentTree::build(1,n,1);
    int m;
    scanf("%d",&m);
    while(m--){
        int xi,yi;
        scanf("%d%d",&xi,&yi);
        printf("%d\n",SegmentTree::query(xi,yi,1,n,1)->mcc);
    }
    return 0;
}

GSS3：带修区间最大子段和

跟不带修有什么区别……

加一个update函数，每次单点修改就重建受影响的子树，时间复杂度$O(\log n)$。

本题完结。（无慈悲）

    void update(int pos,int val,int l,int r,int rt){
        if(l==r){
            node[rt].sum=node[rt].lm=node[rt].rm=node[rt].mcc=val;
            return;
        }
        int m=(l+r)>>1;
        if(pos<=m)update(pos,val,l,m,rt<<1);
        else update(pos,val,m+1,r,rt<<1|1);
        push_up(rt);
    }

GSS5：有限制的区间最大子段和

带不带修都能做，也就是前面问题的延伸，无非多套了层皮。

左右端点均要满足在范围内，直接维护显然没法上手，不过有了刚才问题的启发你应该立马可以想到查询的时候再做一次合并即可。

考虑限制区间的情况。

① 交集为空
此时直接合并。查询左限制区间最大后缀和右限制区间最大前缀相加后与中间部分的sum再求sum即可。
ans=SegmentTree::query(xi,yi,1,n,1)->rm+SegmentTree::query(yi+1,xj-1,n)->sum+SegmentTree::query(xj,yj,1,n,1)->lm;

② 交集不为空
为方便讨论，将限制区间的四个端点按大小顺序排序记为p1 p2 p3 p4，此时左限制区间是[p1,p3]，右限制区间是[p2,p4]。
仍然合并，只是需要考虑的东西多了点。答案可能由三种方法产生，分别是交集的最大子段和、[p1,p2]的最大后缀加上(p2,p4]的最大前缀、[p1,p3]的最大前缀加上(p3,p4]的最大后缀。三者取max合并即可。注意大小关系限制。

本题完结。（无慈悲）

    Node* query(int L,int R,int n){
        if(L>R)return node;
        return query(L,R,1,n,1);
    }

        while(m--){
            int xi,yi,xj,yj;
            scanf("%d%d%d%d",&xi,&yi,&xj,&yj);
            if(yi>=xj){
                int ans=SegmentTree::query(xj,yi,1,n,1)->mcc;
                if(xi<xj)ans=max(ans,SegmentTree::query(xi,xj-1,1,n,1)->rm+SegmentTree::query(xj,yj,1,n,1)->lm);
                if(yi<yj)ans=max(ans,SegmentTree::query(xi,yi,1,n,1)->rm+SegmentTree::query(yi+1,yj,1,n,1)->lm);
                printf("%d\n",ans);
            }else printf("%d\n",SegmentTree::query(xi,yi,1,n,1)->rm+SegmentTree::query(yi+1,xj-1,n)->sum+SegmentTree::query(xj,yj,1,n,1)->lm);
        }

版权声明：本文是原创文章，版权归 无限UCW 所有。

本文链接：https://ucw.moe/archives/solution-gss-5.html

本站所有原创文章采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可。
您可以自由地转载和修改，但请务必注明文章来源并且不可用于商业目的。