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+5;
inline int read(){
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
int n,Q,a,b;
struct Node{
    int sum,mx,lm,rm;
    Node():sum(0),mx(0),lm(0),rm(0){}
}t[N<<2];
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(1,1,n);
    Q=read();
    for(int i=1;i<=Q;i++) a=read(),b=read(),printf("%d
",segQue(1,1,n,a,b).mx);
}