UVALive 3938 "Ray, Pass me the dishes!" 动态最大连续和（线段树）

我不是女神ヾ 2021-12-11 13:31 133阅读 0赞

## 题意：给出一个长度为n的序列, 再给出m个询问, 每个询问是在序列 \[a,b\]\[a,b\] 之间的最大连续和. 要你计算出这个这个区间内最大连续和的区间 \[x,y\](a≤x≤y≤b)\[x,y\](a≤x≤y≤b)。 ##

## 分析：详见《训练指南》P201-202。 ##

## 代码： ##

#include<bits/stdc++.h>
    using namespace std;
    
    const int maxn=500000+10;
    typedef long long ll;
    typedef pair<int,int> par;
    ll a[maxn];
    int n,q,temp,l,r;
    ll sum[maxn];//前缀和,要求一段区间的值就是sum[r]-sum[l-1]
    
    struct node
    {
        int l,r,prer,sufl;//左右节点，最大前缀和终点，最大后缀和起点
        par sub;//结果
    }nodes[maxn<<2];
    ll cal(par x)
    {
        return sum[x.second]-sum[x.first-1];//求区间和
    }
    //比较两个区间和大小
    par cmp(par x,par y)
    {
        ll a=cal(x);
        ll b=cal(y);
        if(a!=b) return a>b?x:y;
        return x<y?x:y;
    }
    //合并
    node com(node x,node y)
    {
        node res;
        res.l=x.l;
        res.r=y.r;
        res.prer=cmp(par(x.l,x.prer),par(x.l,y.prer)).second;//新节点的最大前缀和终点，画个图就能理解
        res.sufl=cmp(par(y.sufl,y.r),par(x.sufl,y.r)).first;//新节点的最大后缀和
        //答案的区间只会有三种情况，要么左边，要么右边，要么中间。
        res.sub=cmp(par(x.sufl,y.prer),cmp(x.sub,y.sub));
        return res;
    }
    void build(int l,int r,int root)
    {
        if(l==r)
        {
            //根节点
            nodes[root].l=nodes[root].r=nodes[root].prer=nodes[root].sufl=l;
            nodes[root].sub=par(l,l);
            return;
        }
        int m=(l+r)/2;
        build(l,m,root*2);//左节点
        build(m+1,r,root*2+1);//右节点
        nodes[root]=com(nodes[root*2],nodes[root*2+1]);//合并
    }
    node query(int l,int r,int root)
    {
        if(nodes[root].l>=l&&nodes[root].r<=r)return nodes[root];
        int m=(nodes[root].l+nodes[root].r)/2;
        node res;
        if(l<=m&&r>m)res=com(query(l,r,root*2),query(l,r,root*2+1));//查询区间包含左右合集
        else if (l<=m)  res=query(l,r,root*2); //l<=m且r<=m，说明只在左边
        else res=query(l,r,root*2+1);   //l>m且r>m说明只在右边
        return res;
    }
    int main()
    {
        int index=1;
        while(scanf("%d%d",&n,&q)!=EOF)
        {
            memset(sum,0,sizeof(sum));
            for(int i=1;i<=n;i++)
            {
                scanf("%lld",&a[i]);
                sum[i]=a[i]+sum[i-1];
            }
            build(1,n,1);
            printf("Case %d:\n",index++);
            for(int i=1;i<=q;++i)
            {
                scanf("%d%d",&l,&r);
                par ans=query(l,r,1).sub;
                printf("%d %d\n",ans.first,ans.second);
            }
        }
        return 0;
    }