SP1043
大不列颠的错误（UKE）求调

#include<bits/stdc++.h>
using namespace std;
struct node{
    int sum,ql,qr,s;
}tree[2000005];
int n,a[500005];
void pushup(node &x,node &l,node &r) {
    x.sum=l.sum+r.sum;
    x.ql=max(l.ql,l.sum+r.ql);
    x.qr=max(r.qr,r.sum+l.qr);
    x.s=max({l.s,r.s,l.qr+r.ql});
}
void build(int x,int l,int r){
    if(l==r){
        tree[x]={a[l],a[l],a[l],a[l]};
        return;
    }
    int mid=(l+r)>>1;
    build(x<<1,l,mid);
    build(x<<1|1,mid+1,r);
    pushup(tree[x],tree[x<<1],tree[x<<1|1]);
}
node query(int x,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr){
		return tree[x];
	}
    int mid=(l+r)>>1;
    if(qr<=mid){
		return query(x<<1,l,mid,ql,qr);
	}
    if(ql>mid){
		return query(x<<1|1, mid+1, r, ql, qr);
	}
    node le=query(x<<1,l,mid,ql,qr);
    node ri=query(x<<1|1,mid+1,r,ql,qr);
    node res;
    pushup(res,le,ri);
    return res;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
		cin>>a[i];
	}
    build(1,1,n);
    int m;
	cin>>m;
    while(m--){
        int l,r;
        cin>>l>>r;
        cout<<query(1,1,n,l,r).s<<"\n";
    }
    return 0;
}