GSS系列

GSS1

直接维护静态区间和即可

#include<bits/stdc++.h>

using namespace std;

const int N=;

int n,a[N];

struct Seg_Tree{int lmax,rmax,dat,sum;}tr[N<<];

inline void pushup(int k){

    tr[k].sum=tr[k<<].sum+tr[k<<|].sum;

    tr[k].lmax=max(tr[k<<].lmax,tr[k<<].sum+tr[k<<|].lmax);

    tr[k].rmax=max(tr[k<<|].rmax,tr[k<<|].sum+tr[k<<].rmax);

    tr[k].dat=max(max(tr[k<<].dat,tr[k<<|].dat),tr[k<<].rmax+tr[k<<|].lmax);

}

inline void build(int k,int l,int r){

    if(l==r)return tr[k].lmax=tr[k].rmax=tr[k].dat=tr[k].sum=a[l],void();

    int mid=(l+r)>>;

    build(k<<,l,mid);

    build(k<<|,mid+,r);

    pushup(k);

}

inline Seg_Tree query(int k,int l,int r,int x,int y){

    if(x<=l&&r<=y)return tr[k];

    int mid=(l+r)>>;

    if(x>mid)return query(k<<|,mid+,r,x,y);

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

    Seg_Tree a=query(k<<,l,mid,x,y),b=query(k<<|,mid+,r,x,y),ans;

    ans.sum=a.sum+b.sum;

    ans.lmax=max(a.lmax,a.sum+b.lmax);

    ans.rmax=max(b.rmax,b.sum+a.rmax);

    ans.dat=max(max(a.dat,b.dat),a.rmax+b.lmax);

    return ans;

}

int main(){

    scanf("%d",&n);

    for(int i=;i<=n;i++)

     scanf("%d",&a[i]);

    build(,,n);

    int q,l,r;

    scanf("%d",&q);

    while(q--){

        scanf("%d%d",&l,&r);

        printf("%d\n",query(,,n,l,r).dat);

    }

}

GSS3

加入单点查询就好了

#include<bits/stdc++.h>

using namespace std;

const int N=;

int n,a[N];

struct Seg_Tree{int lmax,rmax,dat,sum;}tr[N<<];

inline void pushup(int k){

    tr[k].sum=tr[k<<].sum+tr[k<<|].sum;

    tr[k].lmax=max(tr[k<<].lmax,tr[k<<].sum+tr[k<<|].lmax);

    tr[k].rmax=max(tr[k<<|].rmax,tr[k<<|].sum+tr[k<<].rmax);

    tr[k].dat=max(max(tr[k<<].dat,tr[k<<|].dat),tr[k<<].rmax+tr[k<<|].lmax);

}

inline void build(int k,int l,int r){

    if(l==r)return tr[k].lmax=tr[k].rmax=tr[k].dat=tr[k].sum=a[l],void();

    int mid=(l+r)>>;

    build(k<<,l,mid);

    build(k<<|,mid+,r);

    pushup(k);

}

inline Seg_Tree query(int k,int l,int r,int x,int y){

    if(x<=l&&r<=y)return tr[k];

    int mid=(l+r)>>;

    if(x>mid)return query(k<<|,mid+,r,x,y);

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

    Seg_Tree a=query(k<<,l,mid,x,y),b=query(k<<|,mid+,r,x,y),ans;

    ans.sum=a.sum+b.sum;

    ans.lmax=max(a.lmax,a.sum+b.lmax);

    ans.rmax=max(b.rmax,b.sum+a.rmax);

    ans.dat=max(max(a.dat,b.dat),a.rmax+b.lmax);

    return ans;

}

inline void change(int k,int l,int r,int x,int v){

    if(x>r||x<l)return;

    if(l==r&&l==x)return tr[k].lmax=tr[k].rmax=tr[k].dat=tr[k].sum=v,void();

    int mid=(l+r)>>;

    change(k<<,l,mid,x,v);

    change(k<<|,mid+,r,x,v);

    pushup(k);

}

int main(){

    scanf("%d",&n);

    for(int i=;i<=n;i++)

     scanf("%d",&a[i]);

    build(,,n);

    int q,t,l,r;

    scanf("%d",&q);

    while(q--){

        scanf("%d%d%d",&t,&l,&r);

        if(t)printf("%d\n",query(,,n,l,r).dat);

        else change(,,n,l,r);

    }

}