（别跟我提什么普朗克时间）

• 记录

自己写了几组数据，和题解对拍，也没有问题....../kk/kk

代码如下：

#pragma GCC optimize(3)
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cctype>
#include<cstdlib>
#include<iostream>

#define MAXN 500005
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define LL long long

using namespace std;

LL a[MAXN],n,m;

struct Node{

	LL p,q,r,sum;

	Node(LL _p,LL _q,LL _r,LL _s)
		:p(_p),q(_q),r(_r),sum(_s){}
	Node(){}
};

struct SMT{

	Node d[MAXN<<2];

	inline void pushup(LL o){
		d[o].sum=d[lson(o)].sum+d[rson(o)].sum;
		d[o].p=max(max(d[lson(o)].p,d[rson(o)].p),d[lson(o)].r+d[rson(o)].q);
		d[o].q=max(d[lson(o)].q,d[lson(o)].sum+d[rson(o)].q);
		d[o].r=max(d[rson(o)].r,d[rson(o)].sum+d[lson(o)].r);
	}

	inline void build(LL l,LL r,LL o){
		if(l==r){
			d[o]=Node(a[l],a[l],a[l],a[l]);
			return ;
		}
		LL mid=(l+r)>>1;
		build(l,mid,lson(o));
		build(mid+1,r,rson(o));
		pushup(o);
	}

	inline void modify(LL pos,LL k,LL ql,LL qr,LL o){
		if(ql==qr){
			if(ql==pos){
				d[o]=Node(k,k,k,k);
			}
			return ;
		}
		LL mid=(ql+qr)>>1;
		if(pos<=mid)modify(pos,k,ql,mid,lson(o));
		else modify(pos,k,mid+1,qr,rson(o));
		pushup(o);
	}

	inline Node query(LL l,LL r,LL ql,LL qr,LL o){
		if(l<=ql&&qr<=r){
			return d[o];
		}
		LL mid=(ql+qr)>>1;
		Node tmp=Node(-2333333333,-2333333333,-2333333333,-2333333333),t1=Node(-2333333333,-2333333333,-2333333333,-2333333333),t2=Node(-2333333333,-2333333333,-2333333333,-2333333333);
		if(l<=mid){
			t1=query(l,r,ql,mid,lson(o));
		}
		if(r>mid){
			t2=query(l,r,mid+1,qr,rson(o));
		}
		tmp.p=max(max(t1.p,t2.p),t1.r+t2.q);
		tmp.q=max(t1.q,t1.sum+t2.q);
		tmp.r=max(t2.r,t2.sum+t1.r);
		tmp.sum=t1.sum+t2.sum;
		return tmp;
	}

};

SMT tree;

int main(void){

	scanf("%lld",&n);

	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
	}

    scanf("%lld",&m);

	tree.build(1,n,1);

	while(m--){
		LL opt,l,r;
		scanf("%lld%lld",&l,&r);
//		if(opt==1){
			if(l>=r){
				swap(l,r);
			}
			printf("%lld\n",tree.query(l,r,1,n,1).p);
//		}
//		else{
//			tree.modify(l,r,1,n,1);
//		}
	}

	return 0;
}