GSS1

于是我拿合并返回节点的线段树(我也不知道应该叫什么名)水了一下$GSS1$

比$NOIp$之前写的不知道高到哪里去了，并且只用了$\frac{1}{3}$的时间

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

#define lc x<<1

#define rc x<<1|1

#define mid ((l+r)>>1)

#define lson x<<1,l,mid

#define rson x<<1|1,mid+1,r

using namespace std;

typedef long long ll;

const int N=5e5+;

inline int read(){

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

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

    return x*f;

}

int n,Q,a,b;

struct Node{

    int sum,mx,lm,rm;

    Node():sum(),mx(),lm(),rm(){}

}t[N<<];

Node Merge(Node a,Node b){

    Node re;

    re.sum=a.sum+b.sum;

    re.mx=max(a.rm+b.lm,max(a.mx,b.mx));

    re.lm=max(a.lm,a.sum+b.lm);

    re.rm=max(b.rm,b.sum+a.rm);

    return re;

}

void merge(int x){

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

    t[x].mx=max(t[lc].rm+t[rc].lm,max(t[lc].mx,t[rc].mx));

    t[x].lm=max(t[lc].lm,t[lc].sum+t[rc].lm);

    t[x].rm=max(t[rc].rm,t[rc].sum+t[lc].rm);

}

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

    if(l==r) t[x].sum=t[x].mx=t[x].lm=t[x].rm=read();

    else{

        build(lson);

        build(rson);

        merge(x);

    }

}

Node segQue(int x,int l,int r,int ql,int qr){

    if(ql<=l&&r<=qr) return t[x];

    else{

        if(qr<=mid) return segQue(lson,ql,qr);

        if(mid<ql) return segQue(rson,ql,qr);

        return Merge(segQue(lson,ql,qr),segQue(rson,ql,qr));

    }

}

int main(){

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

    n=read();

    build(,,n);

    Q=read();

    for(int i=;i<=Q;i++) a=read(),b=read(),printf("%d\n",segQue(,,n,a,b).mx);

}