[冬令营Day1 T2]sequence

题目描述 Description

给一个长度为N的序列以及Q的询问，每次两个参数l,r，问你序列[l,r]中的最大连续和

输入描述 Input Description

一行二个正整数N,Q。
　　接下来一行N个整数，描述序列A。
　　接下来Q行，每行两个参数L,R，描述一个询问。

输出描述 Output Description

对于每个询问，输出一行一个整数，描述答案。

样例输入 Sample Input

4 3
1 -2 3 2
1 4
1 2
2 2

样例输出 Sample Output

数据范围及提示 Data Size & Hint

测试点编号	数据范围及特殊说明
1,2,3	N,Q≤1000
4,5,6,7	N,Q≤10^5
8,9,10	N≤10^5,Q≤10^6

线段树。对于每个节点，维护三个值。sum,suml,sumr表示该点的最大连续和，最大前缀和和最大后缀和。

#include<iostream>

#include<cmath>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<queue>

using namespace std;

typedef long long LL;

inline int read()

{

    int x=,f=;char c=getchar();

    while(!isdigit(c)){if(c=='-')f=-;c=getchar();}

    while(isdigit(c)){x=x*+c-'';c=getchar();}

    return x*f;

}

const int oo=;

const int maxn=;

int n,q,a[maxn],x,y;

LL pre[maxn],sum[maxn],suml[maxn],sumr[maxn];

void build(int l,int r,int o)

{

    if(l==r)

    {

        suml[o]=sumr[o]=sum[o]=pre[r]-pre[l-];

        return;

    }

    int mid=(l+r)>>,lo=o<<,ro=lo+;

    build(l,mid,lo);

    build(mid+,r,ro);

    sum[o]=max(sum[lo],sum[ro]);

    sum[o]=max(sum[o],sumr[lo]+suml[ro]);

    suml[o]=max(suml[lo],pre[mid]-pre[l-]+suml[ro]);

    sumr[o]=max(sumr[ro],pre[r]-pre[mid]+sumr[lo]);

    return;

}

LL queryl(int x,int y,int l,int r,int o)

{

    if(x==l && y==r) return sumr[o];

    int mid=(l+r)>>,lo=o<<,ro=lo+;

    if(x>mid) return queryl(x,y,mid+,r,ro);

    else

    {

        LL tmp=pre[r]-pre[mid]+queryl(x,mid,l,mid,lo);

        return max(sumr[ro],tmp);

    }

}

LL queryr(int x,int y,int l,int r,int o)

{

    if(x==l && y==r) return suml[o];

    int mid=(l+r)>>,lo=o<<,ro=lo+;

    if(y<=mid) return queryr(x,y,l,mid,lo);

    else

    {

        LL tmp=pre[mid]-pre[l-]+queryr(mid+,y,mid+,r,ro);

        return max(suml[lo],tmp);

    }

}

LL query(int x,int y,int l,int r,int o)

{

    if(x<=l && y>=r)return sum[o];

    int mid=(l+r)>>,lo=o<<,ro=lo+;

    if(y<=mid) return query(x,y,l,mid,lo);

    else if(x>mid) return query(x,y,mid+,r,ro);

    else

    {

        LL ls,rs;

        ls=queryl(x,mid,l,mid,lo);

        rs=queryr(mid+,y,mid+,r,ro);

        return max(max(query(x,mid,l,mid,lo),query(mid+,y,mid+,r,ro)),rs+ls);

    }

}

int main()

{

    freopen("sequence.in","r",stdin);

    freopen("sequence.out","w",stdout);

    n=read();q=read();

    for(int i=;i<=n;i++)a[i]=read(),pre[i]=pre[i-]+a[i];

    build(,n,);

    while(q--)

    {

        x=read();y=read();

        LL tmp=query(x,y,,n,);

        if(tmp<)tmp=;

        printf("%lld\n",tmp);

    }

    return ;

}

对于后三个点肯定没戏，毕竟线段树常数那么大。满分做法好像是整体二分，然而并不会，等着以后来填坑吧。

巴特西

[冬令营Day1 T2]sequence

最新文章

热门文章