【SPOJ】 GSS系列 [线段树][动态区间求最大子段和]

古城微笑少年丶 2021-11-16 05:40 216阅读 0赞

## [SP1043 GSS1 - Can you answer these queries I][]动态区间求最大子段和 ##

动态区间求最大子段和

维护当前区间的和sum 最大前缀和lmx 最大后缀和rmx 最大子段和

洛谷第一篇题解那个dalao码风很赞 当成模板

> 重点在于查询，这里使用了结构体类型定义函数，这样写更加简洁，分情况查询，查询区间左端点在mid右，右端点在mid左，查询区间覆盖节点，查询区间被节点左右区间包含，合并查询类似于PushUp的操作，还是看代码理解

#include<iostream>
    #include<cstdio>
    #include<cmath>
    #include<algorithm>
    using namespace std;
    #define Max(x,y) (x)>(y)?(x):(y)
    #define Min(x,y) (x)>(y)?(y):(x)
    #define ll long long
    #define rg register
    #define lson o<<1
    #define rson o<<1|1
    const int N=200000+5,M=1000000+5,inf=0x3f3f3f3f,P=19650827;
    int n,q,a[N];
    char op;
    template <class t>void rd(t &x){
        x=0;int w=0;char ch=0;
        while(!isdigit(ch)) w|=ch=='-',ch=getchar();
        while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
        x=w?-x:x;
    }
    
    struct SegmentTree{
        int sum,lmx,rmx,mxs;
    }tree[N<<1];
    
    void pushup(int o){
        tree[o].sum=tree[lson].sum+tree[rson].sum;
        tree[o].lmx=Max(tree[lson].lmx,tree[lson].sum+tree[rson].lmx);//最大前缀和 
        tree[o].rmx=Max(tree[rson].rmx,tree[rson].sum+tree[lson].rmx);//最大后缀和
        tree[o].mxs=Max(Max(tree[lson].mxs,tree[rson].mxs),tree[lson].rmx+tree[rson].lmx);
    }
    void buildtree(int o,int l,int r){
        if(l==r) {tree[o].sum=tree[o].mxs=tree[o].lmx=tree[o].rmx=a[l];return;}
        int mid=l+r>>1;
        buildtree(lson,l,mid),buildtree(rson,mid+1,r);
        pushup(o);
    } 
    
    SegmentTree query(int o,int l,int r,int x,int y){
        if(x<=l&&r<=y) return tree[o];
        int mid=(l+r)>>1;
        if(y<=mid) return query(lson,l,mid,x,y);//完全位于左区间 
        else if(x>mid) return query(rson,mid+1,r,x,y);//完全位于右区间 
        else{
        //与左、右区间都有交集 
            SegmentTree ls,rs,ans;
            ls=query(lson,l,mid,x,y),rs=query(rson,mid+1,r,x,y);
            ans.sum=ls.sum+rs.sum;
            ans.lmx=Max(ls.lmx,ls.sum+rs.lmx);
            ans.rmx=Max(rs.rmx,rs.sum+ls.rmx);
            ans.mxs=Max(Max(ls.mxs,rs.mxs),ls.rmx+rs.lmx);
            return ans;
        } 
    }
    
    int main(){
        rd(n);
        for(int i=1;i<=n;++i) rd(a[i]);
        buildtree(1,1,n);
        rd(q);
        for(int i=1,x,y;i<=q;++i){
            rd(x),rd(y);
            printf("%d\n",query(1,1,n,x,y).mxs);
        }
        return 0;
    }

## [SP1557 GSS2 - Can you answer these queries II][] ##

给出n 个数，q 次询问，求最大子段和，相同的数只算一次

你鲨了我叭 一堆细节 考场打死我都调不出来 就比上面那题多了一个条件 难度蹭蹭上涨

维护一段区间的sum historymaxsum 还有tag：add maxadd

就像[\[SDOI2009\]HH的项链][SDOI2009_HH]一样有要求去重 我们得考虑离线来做

然后就是1mol的细节 结合代码好好思考 题还是个好题QAQ

#include<iostream>
    #include<cstdio>
    #include<queue>
    #include<cstring>
    #include<cmath>
    #include<stack>
    #include<algorithm>
    using namespace std;
    #define Max(x,y) (x)>(y)?(x):(y)
    #define Min(x,y) (x)>(y)?(y):(x)
    #define ll long long
    #define rg register
    #define lson o<<1
    #define rson o<<1|1
    const int N=100000+5,M=1000000+5,inf=0x3f3f3f3f,P=19650827;
    ll n,m,a[N],pre[N],id[N<<1],ans[N];
    template <class t>void rd(t &x){
        x=0;int w=0;char ch=0;
        while(!isdigit(ch)) w|=ch=='-',ch=getchar();
        while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
        x=w?-x:x;
    }
    
    struct SegmentTree{
        ll hismx,sum,add,mxadd;
        SegmentTree(){hismx=sum=add=mxadd=0;}
    }tree[N<<2];
    
    void pushdown(int o){
        //注意这几个的更新顺序 
        tree[lson].hismx=Max(tree[lson].hismx,tree[lson].sum+tree[o].mxadd);
        tree[rson].hismx=Max(tree[rson].hismx,tree[rson].sum+tree[o].mxadd);
        //historymaxsum用儿子的sum+节点historymaxtag来更新 
        tree[lson].sum+=tree[o].add,tree[rson].sum+=tree[o].add;
        tree[lson].mxadd=Max(tree[lson].mxadd,tree[o].mxadd+tree[lson].add);
        tree[rson].mxadd=Max(tree[rson].mxadd,tree[o].mxadd+tree[rson].add);
        //historymaxtag用儿子的sumtag+节点historymaxtag 
        tree[lson].add+=tree[o].add,tree[rson].add+=tree[o].add;
        tree[o].mxadd=tree[o].add=0;
    }
    void pushup(int o){
        tree[o].sum=Max(tree[lson].sum,tree[rson].sum);
        tree[o].hismx=Max(tree[lson].hismx,tree[rson].hismx);
    }
    void update(int o,int l,int r,int x,int y,ll k){
        if(r<x||l>y) return;
        if(x<=l&&r<=y){
        //在区间内 
            tree[o].sum+=k;
            tree[o].hismx=Max(tree[o].hismx,tree[o].sum);
            tree[o].add+=k;
            tree[o].mxadd=Max(tree[o].mxadd,tree[o].add);
            return;
        }
        pushdown(o);
        int mid=l+r>>1;
        update(lson,l,mid,x,y,k),update(rson,mid+1,r,x,y,k);
        pushup(o);
    }
    
    SegmentTree query(int o,int l,int r,int x,int y){
        if(x<=l&&r<=y) return tree[o];
        pushdown(o);
        int mid=l+r>>1;
        if(y<=mid) return query(lson,l,mid,x,y);//完全在左边 
        else if(x>mid) return query(rson,mid+1,r,x,y);//完全在右边
        else{
            SegmentTree ans,ls,rs;
            ls=query(lson,l,mid,x,y),rs=query(rson,mid+1,r,x,y);
            ans.hismx=Max(ls.hismx,rs.hismx);
            return ans;
        }
    }
    
    struct node{
        int x,y,pos;}ask[N];
    bool cmp(node x,node y){
        return x.y<y.y;}
    int main(){
    //    freopen("in.txt","r",stdin);
        rd(n);
        for(int i=1;i<=n;++i) rd(a[i]),pre[i]=id[a[i]+N],id[a[i]+N]=i;
        rd(m);
        for(int i=1;i<=m;++i) rd(ask[i].x),rd(ask[i].y),ask[i].pos=i;
        sort(ask+1,ask+1+m,cmp);
        int pos=1;
        for(int i=1;i<=n;++i){
            update(1,1,n,pre[i]+1,i,a[i]);
            for(;pos<=m&&ask[pos].y<=i;++pos){
                ans[ask[pos].pos]=query(1,1,n,ask[pos].x,ask[pos].y).hismx;
            }
        }
        for(int i=1;i<=m;++i) printf("%lld\n",ans[i]);
        return 0;
    }

## [SP1716 GSS3 - Can you answer these queries III][] 动态区间求最大子段和+单点修改 ##

其实是一样的 然后单点修改又和buildtree长得差不多

#include<iostream>
    #include<cstdio>
    #include<cmath>
    #include<algorithm>
    using namespace std;
    #define Max(x,y) (x)>(y)?(x):(y)
    #define Min(x,y) (x)>(y)?(y):(x)
    #define ll long long
    #define rg register
    #define lson o<<1
    #define rson o<<1|1
    const int N=200000+5,M=1000000+5,inf=0x3f3f3f3f,P=19650827;
    int n,q,a[N];
    template <class t>void rd(t &x){
        x=0;int w=0;char ch=0;
        while(!isdigit(ch)) w|=ch=='-',ch=getchar();
        while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
        x=w?-x:x;
    }
    
    struct SegmentTree{
        int sum,lmx,rmx,mxs;}tree[N];
    
    void pushup(int o){
        tree[o].sum=tree[lson].sum+tree[rson].sum;
        tree[o].lmx=Max(tree[lson].lmx,tree[lson].sum+tree[rson].lmx);
        tree[o].rmx=Max(tree[rson].rmx,tree[rson].sum+tree[lson].rmx);
        tree[o].mxs=Max(Max(tree[lson].mxs,tree[rson].mxs),tree[lson].rmx+tree[rson].lmx);
    }
    void buildtree(int o,int l,int r){
        if(l==r){tree[o].sum=tree[o].lmx=tree[o].rmx=tree[o].mxs=a[l];return;}
        int mid=l+r>>1;
        buildtree(lson,l,mid),buildtree(rson,mid+1,r);
        pushup(o);
    }
    
    void modify(int o,int l,int r,int x,int k){
        if(l==r){tree[o].sum=tree[o].lmx=tree[o].rmx=tree[o].mxs=k;return;}
        int mid=l+r>>1;
        if(x<=mid) modify(lson,l,mid,x,k);
        else modify(rson,mid+1,r,x,k);
        pushup(o);
    }
    
    SegmentTree query(int o,int l,int r,int x,int y){
        if(x<=l&&r<=y) return tree[o];
        int mid=l+r>>1;
        if(y<=mid) return query(lson,l,mid,x,y);
        else if(x>mid) return query(rson,mid+1,r,x,y);
        else{
            SegmentTree ls,rs,ans;
            ls=query(lson,l,mid,x,y),rs=query(rson,mid+1,r,x,y);
            ans.sum=ls.sum+rs.sum;
            ans.lmx=Max(ls.lmx,ls.sum+rs.lmx);
            ans.rmx=Max(rs.rmx,rs.sum+ls.rmx);
            ans.mxs=Max(Max(ls.mxs,rs.mxs),ls.rmx+rs.lmx);
            return ans;
        }
    }
    
    int main(){
        rd(n);
        for(int i=1;i<=n;++i) rd(a[i]);
        buildtree(1,1,n);
        rd(q);
        for(int i=1,x,y,op;i<=q;++i){
            rd(op),rd(x),rd(y);
            if(op==1) printf("%d\n",query(1,1,n,x,y).mxs);
            else modify(1,1,n,x,y);
        }
        return 0;
    }

## [SP2713 GSS4 - Can you answer these queries IV][] 线段树求区间和 区间开方 ##

[上帝造题的七分钟2 / 花神游历各国 \[线段树\]][2 _ _]

和花神游历各国是一样的 只是我死于输出.... 开始忘了Case \#1后面的： 然后找到了一激动 改成Case \#%d\\n: 我还有什么话可说呢QAQ

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

/*
    Case #1后面有个：！！！QAQ 
    */
    #include<iostream>
    #include<cstdio>
    #include<cmath>
    #include<algorithm>
    using namespace std;
    #define Max(x,y) (x)>(y)?(x):(y)
    #define Min(x,y) (x)>(y)?(y):(x)
    #define ll long long
    #define rg register
    #define lson o<<1
    #define rson o<<1|1
    const int N=100000+5,M=1000000+5,inf=0x3f3f3f3f,P=19650827;
    int n,m,cas=0;
    ll a[N],sum[N<<2],mx[N<<2];
    template <class t>void rd(t &x){
        x=0;int w=0;char ch=0;
        while(!isdigit(ch)) w|=ch=='-',ch=getchar();
        while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
        x=w?-x:x;
    }
    
    void pushup(int o){
        sum[o]=sum[lson]+sum[rson];
        mx[o]=Max(mx[lson],mx[rson]);
    }
    
    void update(int o,int l,int r,int x,int y){
        if(r<x||l>y) return;
        if(mx[o]<=1&&x<=l&&r<=y) return;
        if(l==r) {mx[o]=sum[o]=floor(sqrt(sum[o]));return;}
        int mid=l+r>>1;
        update(lson,l,mid,x,y),update(rson,mid+1,r,x,y);
        pushup(o);
    }
    
    ll query(int o,int l,int r,int x,int y){
        if(r<x||l>y) return 0;
        if(x<=l&&r<=y) return sum[o];
        int mid=l+r>>1;ll ans=0;
        ans+=query(lson,l,mid,x,y);ans+=query(rson,mid+1,r,x,y);
        return ans;
        
    }
    
    void buildtree(int o,int l,int r){
        if(l==r) {sum[o]=mx[o]=a[l];return;}
        int mid=l+r>>1;
        buildtree(lson,l,mid),buildtree(rson,mid+1,r);
        pushup(o);
    }
    
    int main(){
    //    freopen("in.txt","r",stdin);
        while(scanf("%lld",&n)==1){
            printf("Case #%d:\n",++cas);
            for(int i=1;i<=n;++i) rd(a[i]);
            buildtree(1,1,n);
            rd(m);
            for(int i=1,op,x,y;i<=m;++i){
                rd(op),rd(x),rd(y);
                if(x>y) swap(x,y);
                if(op==1) printf("%lld\n",query(1,1,n,x,y));
                else update(1,1,n,x,y);
            }
            puts("");
        }
        return 0;
    }

GSS4

## [SP2916 GSS5 - Can you answer these querie][] ##

给定一个序列。查询左端点在\[x1, y1\]之间，且右端点在\[x2, y2\]之间的最大子段和，数据保证x1≤x2,y1≤y2，但是不保证端点所在的区间不重合

考虑这个的情况我真的要考虑die了 我开始是把所有的情况都讨论出来QAQ 其实在query查询时加一个判断为空就好了

#include<iostream>
    #include<cstdio>
    #include<cmath>
    #include<algorithm>
    using namespace std;
    #define Max(x,y) (x)>(y)?(x):(y)
    #define Min(x,y) (x)>(y)?(y):(x)
    #define ll long long
    #define rg register
    #define lson o<<1
    #define rson o<<1|1
    const int N=200000+5,M=1000000+5,inf=0x3f3f3f3f,P=19650827;
    int T,n,q,a[N];
    template <class t>void rd(t &x){
        x=0;int w=0;char ch=0;
        while(!isdigit(ch)) w|=ch=='-',ch=getchar();
        while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
        x=w?-x:x;
    }
    
    struct SegmentTree{
        int sum,lmx,rmx,mxs;
        SegmentTree(){sum=lmx=rmx=mxs=0;}
    }tree[N<<1],blank;
    
    void pushup(int o){
        tree[o].sum=tree[lson].sum+tree[rson].sum;
        tree[o].lmx=Max(tree[lson].lmx,tree[lson].sum+tree[rson].lmx);//最大前缀和 
        tree[o].rmx=Max(tree[rson].rmx,tree[rson].sum+tree[lson].rmx);//最大后缀和
        tree[o].mxs=Max(Max(tree[lson].mxs,tree[rson].mxs),tree[lson].rmx+tree[rson].lmx);
    }
    void buildtree(int o,int l,int r){
        if(l==r) {tree[o].sum=tree[o].mxs=tree[o].lmx=tree[o].rmx=a[l];return;}
        int mid=l+r>>1;
        buildtree(lson,l,mid),buildtree(rson,mid+1,r);
        pushup(o);
    } 
    
    SegmentTree query(int o,int l,int r,int x,int y){
        if(x>y) return blank;
        if(x<=l&&r<=y) return tree[o];
        int mid=(l+r)>>1;
        if(y<=mid) return query(lson,l,mid,x,y);//完全位于左区间 
        else if(x>mid) return query(rson,mid+1,r,x,y);//完全位于右区间 
        else{
        //与左、右区间都有交集 
            SegmentTree ls,rs,ans;
            ls=query(lson,l,mid,x,y),rs=query(rson,mid+1,r,x,y);
            ans.sum=ls.sum+rs.sum;
            ans.lmx=Max(ls.lmx,ls.sum+rs.lmx);
            ans.rmx=Max(rs.rmx,rs.sum+ls.rmx);
            ans.mxs=Max(Max(ls.mxs,rs.mxs),ls.rmx+rs.lmx);
            return ans;
        } 
    }
    
    int main(){
    //    freopen("in.txt","r",stdin);
        rd(T);
        while(T--){
            rd(n);
            for(int i=1;i<=n;++i) rd(a[i]);
             buildtree(1,1,n);
             rd(q);
              int x1,y1,x2,y2,ans,ans1;
               for(int i=1;i<=q;++i){
                    rd(x1),rd(y1),rd(x2),rd(y2),ans=0;
                    if(y1<x2){
                    ans+=query(1,1,n,y1,x2).sum;
                    ans+=Max(query(1,1,n,x1,y1-1).rmx,0);
                    ans+=Max(query(1,1,n,x2+1,y2).lmx,0);
                        
                    } 
                    else{
                        ans=query(1,1,n,x2,y1).mxs;
                        ans=Max(ans,query(1,1,n,x2,y1).lmx +query(1,1,n,x1,x2-1).rmx);
                    ans=Max(ans,query(1,1,n,y1+1,y2).lmx+query(1,1,n,x2,y1).rmx);
                    ans1=query(1,1,n,x2,y1).sum;ans1+=Max(0,query(1,1,n,x1,x2-1).rmx);ans1+=Max(0,query(1,1,n,y1+1,y2).lmx);
                    ans=Max(ans,ans1);
                }
                printf("%d\n",ans);
            }
        }
        return 0;
    }

转载于:https://www.cnblogs.com/lxyyyy/p/11195791.html

[SP1043 GSS1 - Can you answer these queries I]: https://www.luogu.org/problemnew/show/SP1043
[SP1557 GSS2 - Can you answer these queries II]: https://www.luogu.org/problemnew/show/SP1557
[SDOI2009_HH]: https://www.cnblogs.com/lxyyyy/p/11179777.html
[SP1716 GSS3 - Can you answer these queries III]: https://www.luogu.org/problemnew/show/SP1716
[SP2713 GSS4 - Can you answer these queries IV]: https://www.luogu.org/problemnew/show/SP2713
[2 _ _]: https://www.cnblogs.com/lxyyyy/p/11164189.html
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211116/8574a49b318244c684c469465d3f2db2.png
[SP2916 GSS5 - Can you answer these querie]: https://www.luogu.org/problemnew/show/SP2916