悬关

哪位dalao绑定了个人账户，帮本蒟蒻提交一下，不胜感激。

//轻喷

#include<bits/stdc++.h>
using namespace std;
const int N=5e4+10;
int a[N],n,m,xx,yy;
struct node{
	int l,r,num/*总和*/,mxmn/*最大子权和*/,bknm/*最大后缀和*/,frtnm/*最大前缀和*/;
}tree[4*N];
struct node2{
	int num/*总和*/,mxmn/*最大子权和*/,bknm/*最大后缀和*/,frtnm/*最大前缀和*/;
};
void pushup(int k){
	tree[k].num=tree[k*2].num+tree[k*2+1].num;
	tree[k].bknm=max(tree[k*2+1].bknm,tree[k*2+1].num+tree[k*2].bknm);
	tree[k].frtnm=max(tree[k*2].frtnm,tree[k*2].num+tree[k*2+1].frtnm);
	tree[k].mxmn=max(tree[k*2].mxmn,max(tree[k*2+1].mxmn,tree[k*2].bknm+tree[k*2+1].frtnm));
}
void build(int k,int l,int r){
	tree[k].l=l;
	tree[k].r=r;
	if(l==r){
		tree[k].num=a[l];
		int o=max(0,a[l]);
		tree[k].mxmn=o;
		tree[k].frtnm=o;
		tree[k].bknm=o;
		return;
	}
	int mid=(l+r)/2;
	build(k*2,l,mid);//left_tree
	build(k*2+1,mid+1,r);//ringt_tree
	pushup(k);
}
node2 workdata(node2 x,node2 y){
	node2 g;
	g.num=x.num+y.num;
	g.bknm=max(y.bknm,y.num+y.bknm);
	g.frtnm=max(x.frtnm,x.num+y.frtnm);
	g.mxmn=max(x.mxmn,max(y.mxmn,x.bknm+y.frtnm));
	return g;
}
node2 query(int k,int l,int r){
	if(l<=tree[k].l&&tree[k].r<=r){
		node2 g;
		g.bknm=tree[k].bknm;
		g.num=tree[k].num;
		g.frtnm=tree[k].frtnm;
		g.mxmn=tree[k].mxmn;
		return g;
	}
	int mid=(tree[k].l+tree[k].r)/2;
	node2 rtnl,rtnr;
	bool qsl=0,qsr=0;
	if(l<=mid){
		qsl=1;
		rtnl=query(k*2,l,r);
	}
	//left
	if(mid+1<=r){
		qsr=1;
		rtnr=query(k*2+1,l,r);
	}
	//right
	if(qsr==0)return rtnl;
	if(qsl==0)return rtnr;
	return workdata(rtnl,rtnr);
} 
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	build(1,1,n);
	cin>>m;
	for(int i=1;i<=m;i++){
		cin>>xx>>yy;
		node2 g=query(1,xx,yy);
		cout<<g.mxmn<<endl;
	}
	return 0;
}