SPOJ GSS1 简单区间合并

题意：

题目描述

给出了序列 \(A_1,A_2,\cdots,A_N\)。 \((a_i\le 15007,1\le N\le 50000)\)。

查询定义如下： 查询 \((x,y)=\max\{a_i+a_{i+1}+\cdots+a_j;x≤i≤j≤y\}\)。

给定 \(M\) 个查询，程序必须输出这些查询的结果。

输入输出格式

输入格式：

• 输入文件的第一行包含整数 \(N\)。
• 在第二行，有 \(N\) 个数字 \(A_i\)。
• 第三行包含整数 \(M\)。
• 在接下来的 \(M\) 行中，第 \(i\) 行包含两个数字 \(x_i\) 和 \(y_i\)。

输出格式：

您的程序应该输出 \(M\) 个查询的结果，每一行一个查询。

要求查询 \([x,y]\) 区间的最大连续子序列和

每个节点维护 4 个值

\(ans_u\) ：\(u\) 节点代表区间的最大连续子序列和

\(lans_u\) ：\(u\) 节点代表区间的最大连续子序列和（限制这个子序列的左端点必须为 \(u\) 节点代表区间的左端点

\(rans_u\) ：\(u\) 节点代表区间的最大连续子序列和（限制这个子序列的右端点必须为 \(u\) 节点代表区间的右端点

\(sum_u\)：\(u\) 节点代表区间的数字和

更新的时候：（\(lson\) 为左儿子，\(rson\) 为右儿子

显然，\(sum_u=sum_{lson}+sum_{rson}\)
\[ ans_u=\max(\max(ans_{lson},ans_{rson}),rans_{lson}+lans_{rson}) \]
\(u\) 的区间的最大连续子序列和可以由 \(lson\) 或 \(rson\) 的区间的最大连续子序列和取 \(\max\) 得来

也可以通过 \(lson\) 的 \(rans\) 和 \(rson\) 的 \(lans\) 拼接得来
\[ lans_u=\max(lans_{lson},sum_{lson}+lans_{rson}) \]
\(lans_u\) 可以从 \(lson\) 的 \(lans\) 直接得来，也可以通过 \(lson\) 的整段和 \(rson\) 的 \(lans\) 拼接得来

\(rans_u\) 也类似
\[ rans_u=\max(rans_{rson},sum_{rson}+rans_{lson}) \]
这个在 pushup 和查询的时候用就好了

// This code Wrote By chtholly_micromaker(MicroMaker)
#include <cstdio>
#include <cctype>
#include <algorithm>
#define reg register
#define int long long
#define rt (u>>1)
#define lson (u<<1)
#define rson (u<<1|1)
#define n(x,y,z,t) (Node){x,y,z,t}
using namespace std;
const int MaxN=50001;
struct Node
{
    int lsum,rsum,sum,maxsum;
}tr[MaxN<<2];
template <class t> inline void rd(t &s)
{
    s=0;
    reg int f=1;
    reg char c=getchar();
    while(!isdigit(c))
    {
        if(c=='-')
            f=-1;
        c=getchar();
    }
    while(isdigit(c))
        s=(s<<3)+(s<<1)+(c^48),c=getchar();
    s*=f;
    return;
}
int n,m;
int a[MaxN];
inline void pushup(int u)
{
    tr[u].sum=tr[lson].sum+tr[rson].sum;
    tr[u].lsum=max(tr[lson].lsum,tr[lson].sum+tr[rson].lsum);
    tr[u].rsum=max(tr[rson].rsum,tr[lson].rsum+tr[rson].sum);
    tr[u].maxsum=max(tr[lson].maxsum,tr[rson].maxsum);
    tr[u].maxsum=max(tr[u].maxsum,tr[lson].rsum+tr[rson].lsum);
    return;
}
inline void buildtr(int u,int l,int r)
{
    if(l==r)
    {
        tr[u]=n(a[l],a[l],a[l],a[l]);
//      printf("build %d %d %d %d %d %d\n",l,r,tr[u].sum,tr[u].maxsum,tr[u].lsum,tr[u].rsum);
        return;
    }
    reg int mid=(l+r)>>1;
    buildtr(lson,l,mid);
    buildtr(rson,mid+1,r);
    pushup(u);
//  printf("build %d %d %d %d %d %d\n",l,r,tr[u].sum,tr[u].maxsum,tr[u].lsum,tr[u].rsum);
    return;
}
inline Node query(int u,int l,int r,int ql,int qr)
{
    if(ql<=l&&r<=qr)
        return tr[u];
    reg int mid=(l+r)>>1;
    if(qr<=mid)
        return query(lson,l,mid,ql,qr);
    if(mid<ql)
        return query(rson,mid+1,r,ql,qr);   
    reg Node a,b,res;
    a=query(lson,l,mid,ql,qr);
    b=query(rson,mid+1,r,ql,qr);
    res.sum=a.sum+b.sum;
    res.maxsum=max(max(a.maxsum,b.maxsum),a.rsum+b.lsum);
    res.lsum=max(a.lsum,b.lsum+a.sum);
    res.rsum=max(b.rsum,a.rsum+b.sum);
    return res;
}
signed main(void)
{
    reg int x,y;
    rd(n);
    for(int i=1;i<=n;++i)
        rd(a[i]);
    buildtr(1,1,n);
    rd(m);
    for(int i=1;i<=m;++i)
    {
        rd(x);rd(y);
        printf("%lld\n",query(1,1,n,x,y).maxsum);
    }
    return 0;
}

SPOJ GSS1 简单区间合并

原文：https://www.cnblogs.com/chinesepikaync/p/12439158.html