SP1043 GSS1

题目链接

简单说就是带修的查询区间最大子段和，用线段树维护即可

对于每个区间，我们肯定要记录它的最大子段和\(v\)，但是怎么维护呢？

我们可以记录下从区间左端点开始的最大子段和\(v1\)，从右端点开始的最大子段和\(v2\)以及区间和\(sum\)

那么\(t[p].sum=t[lc].sum+t[rc].sum\)

\(t[p].v1=max(t[lc].v1,t[lc].sum+t[rc].v1)\)

\(t[p].v2=max(t[rc].v 2,t[rc].sum+t[lc].v2)\)

\(t[p].v=max(t[lc].v2+t[rc].v1,t[lc].v,t[rc].v)\)

正确性应该很显然不需要再给出证明了吧

下放代码

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cctype>

#define ll long long

#define gc getchar

#define maxn 50005

using namespace std;

inline ll read(){

    ll a=0;int f=0;char p=gc();

    while(!isdigit(p)){f|=p=='-';p=gc();}

    while(isdigit(p)){a=(a<<3)+(a<<1)+(p^48);p=gc();}

    return f?-a:a;

}int n,m;

struct ahaha{

    int v,v1,v2,sum;

}t[maxn<<2];

#define lc p<<1

#define rc p<<1|1

inline void pushup(int p){

    t[p].sum=t[lc].sum+t[rc].sum;

    t[p].v1=max(t[lc].v1,t[lc].sum+t[rc].v1);

    t[p].v2=max(t[rc].v2,t[rc].sum+t[lc].v2);

    t[p].v=max(t[lc].v2+t[rc].v1,max(t[lc].v,t[rc].v));

}

void build(int p,int l,int r){

    if(l==r){t[p].v=t[p].v1=t[p].v2=t[p].sum=read();return;}

    int m=l+r>>1;

    build(lc,l,m);build(rc,m+1,r);

    pushup(p);

}

ahaha query(int p,int l,int r,int L,int R){

    if(l>R||r<L)return {-214748,-214748,-214748,-214748};

    if(L<=l&&r<=R)return t[p];

    int m=l+r>>1;

    ahaha l1=query(lc,l,m,L,R),r1=query(rc,m+1,r,L,R),i;

    i.sum=l1.sum+r1.sum;

    i.v1=max(l1.v1,l1.sum+r1.v1);

    i.v2=max(r1.v2,r1.sum+l1.v2);

    i.v=max(l1.v2+r1.v1,max(l1.v,r1.v));

    return i;

}

inline void solve(){

    int x=read(),y=read();

    printf("%d\n",query(1,1,n,x,y).v);

}

int main(){

    n=read();

    build(1,1,n);

    m=read();

    while(m--)

        solve();

    return 0;

}

巴特西

SP1043 GSS1

最新文章

热门文章