经典线段树 UVALive 3938/UVA 1400

题意：就是相当于动规里面的求最大连续子串，不同的是，这里需要读入一个区间x,y,输出的区间 a,b 且x<=a<=b<=y,使得a b的连续子串最长，而且询问次数达到了10的五次方。

我是在大白书上看到这个题，一开始想简单了，就照着刘汝佳的思路写，线段树里只存了前缀最大和，后缀最大和，总最大和，但题目要求输出区间，明显的需要添加记录维护区间位置的，而且不止要存储 a,b，还要存pre suf，前缀后缀的边界位置。我第一次写的时候意识到了，但是那个时候已经有点混乱了，我以为在查询的时候，根据最大和就能确定区间。。。结果真是。。。智商被碾压。

还有个令人心酸的地方，直接导致我WA了整整一版，。。。尼玛，我记得校队选拔赛的时候也是同样的问题卡了我最后一个简单的题目，就是我用的中间变量暂存最大和，我知道最大和肯定会超过int，所以之前就设置了ll，但尼玛我定义中间变量的时候，居然下意识还是用的int。。。。。检查了我N多遍才查出来。。尼玛太心酸了。。一定要注意细节

#include <iostream>
#include <cstdio>
#include <cstring>
#define Lson x<<1,l,mid
#define Rson (x<<1|1),mid+1,r
#define N 500030
using namespace std;

struct node//线段树节点只需要记录前缀最右边间位置pre，类似的后缀suf，以及真正的解区间，vx，vy
{
    int vx,vy;
    int suf,pre;
} tree[N*3];
long long s[N];
void getup(int x,int l,int r)
{
    if (s[tree[x<<1].pre]-s [l-1]>=s[tree[x<<1|1].pre]-s[l-1]){
        tree[x].pre=tree[x<<1].pre;
    }
    else{
        tree[x].pre=tree[x<<1|1].pre;
    }
    if (s[r]-s[tree[x<<1].suf-1]>=s[r]-s[tree[x<<1|1].suf-1]){
        tree[x].suf=tree[x<<1].suf;
    }
    else{
        tree[x].suf=tree[x<<1|1].suf;
    }
    long long v1=s[tree[x<<1].vy]-s[tree[x<<1].vx-1];
    long long v2=s[tree[x<<1|1].vy]-s[tree[x<<1|1].vx-1];
    long long v0=s[tree[x<<1|1].pre]-s[tree[x<<1].suf-1];
    if (v1>=v2){
        tree[x].vx=tree[x<<1].vx;
        tree[x].vy=tree[x<<1].vy;
    }
    else{
        tree[x].vx=tree[x<<1|1].vx;
        tree[x].vy=tree[x<<1|1].vy;
    }
    if (v0==s[tree[x].vy]-s[tree[x].vx-1]){
        if (tree[x<<1].suf<tree[x].vx){
            tree[x].vx=tree[x<<1].suf;
            tree[x].vy=tree[x<<1|1].pre;
        }
        else if (tree[x<<1].suf==tree[x].vx && tree[x<<1|1].pre<tree[x].vy){
            tree[x].vy=tree[x<<1|1].pre;
        }
    }
    if (v0>s[tree[x].vy]-s[tree[x].vx-1]){
        tree[x].vx=tree[x<<1].suf;
        tree[x].vy=tree[x<<1|1].pre;
    }

}
void build(int x,int l,int r)
{
    if (l==r)
    {
        tree[x].pre=tree[x].suf=tree[x].vy=tree[x].vx=l;
        return;
    }
    int mid=(l+r)/2;
    build(Lson);
    build(Rson);
    getup(x,l,r);
}
node query(int st,int e,int x,int l,int r)
{
    if (st<=tree[x].vx && tree[x].vy<=e){
        return tree[x];
    }
    int mid=(l+r)/2;
    if (st>mid){
        return query(st,e,Rson);
    }
    if (e<=mid){
        return query(st,e,Lson);
    }
    node a=query(st,e,Lson);
    node b=query(st,e,Rson);
    node c;
    if (s[a.vy]-s[a.vx-1]>=s[b.vy]-s[b.vx-1]){
        c.vx=a.vx;
        c.vy=a.vy;
    }
    else {
        c.vx=b.vx;
        c.vy=b.vy;
    }
    if (s[a.pre]-s[st-1]>=s[b.pre]-s[st-1]){
        c.pre=a.pre;
    }
    else{
        c.pre=b.pre;
    }
    if (s[e]-s[a.suf-1]>=s[e]-s[b.suf-1]){
        c.suf=a.suf;
    }
    else{
        c.suf=b.suf;
    }
    if (s[b.pre]-s[a.suf-1]==s[c.vy]-s[c.vx-1]){
        if (a.suf<c.vx){
            c.vx=a.suf;
            c.vy=b.pre;
        }
        if (a.suf==c.vx && b.pre<c.vy){
            c.vy=b.pre;
        }
    }
    else
    if (s[b.pre]-s[a.suf-1]>s[c.vy]-s[c.vx-1]){
        c.vx=a.suf;
        c.vy=b.pre;
    }
    return c;
}
int main()
{
    int n,m;
    int counts=0;
    while (scanf("%d%d",&n,&m)!=EOF)
    {
        int i,j,k;
        memset(s,0,sizeof s);
        long long tt;
        for (i=1;i<=n;i++){
            scanf("%lld",&tt);
            s[i]=s[i-1]+tt;
        }
        build(1,1,n);
        printf("Case %d:
",++counts);
        for (i=1;i<=m;i++){
            int ss,e;
            scanf("%d%d",&ss,&e);
            node ans=query(ss,e,1,1,n);

            printf("%d %d
",ans.vx,ans.vy);
        }
    }
    return 0;
}

经典线段树 UVALive 3938/UVA 1400

相关推荐