山海经 - Go灬Fire - 378984

记录编号	378984	评测结果	AAAAAAAA
题目名称	山海经	最终得分	100
用户昵称	Go灬Fire	是否通过	通过
代码语言	C++	运行时间	0.969 s
提交时间	2017-03-05 16:07:19	内存使用	32.35 MiB
显示代码纯文本
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long
#define Inf 2e9
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
const int maxn=150000;
struct Node{
	LL ml,mr,Max,sum;
	int l,r,ll,rr;
	int L,R;
	//Node(){};
	Node(LL x=-Inf){l=r=Inf;ml=mr=Max=sum=x;}
}a[maxn<<2];
int n,T;
void pushup(int rt,int l,int r){
	a[rt].sum=a[rt<<1].sum+a[rt<<1|1].sum;
	a[rt].L=a[rt<<1].L;a[rt].R=a[rt<<1|1].R;
	a[rt].ml=a[rt<<1].ml;a[rt].ll=a[rt<<1].ll;
	if(a[rt<<1].ml==a[rt<<1].sum){
		if(a[rt].ml<a[rt<<1].ml+a[rt<<1|1].ml){
			a[rt].ml=a[rt<<1].ml+a[rt<<1|1].ml;
			a[rt].ll=a[rt<<1|1].ll;
		}
	}
	if(a[rt<<1].sum+a[rt<<1|1].ml>a[rt].ml){//
		a[rt].ml=a[rt<<1].sum+a[rt<<1|1].ml;
		a[rt].ll=a[rt<<1|1].ll;
	}
	
	a[rt].mr=a[rt<<1|1].mr;a[rt].rr=a[rt<<1|1].rr;
	if(a[rt<<1|1].mr==a[rt<<1|1].sum){
		if(a[rt].mr<=a[rt<<1|1].mr+a[rt<<1].mr){
			a[rt].mr=a[rt<<1|1].mr+a[rt<<1].mr;
			a[rt].rr=a[rt<<1].rr;
		}
	}
	if(a[rt<<1|1].sum+a[rt<<1].mr>a[rt].mr){//
		a[rt].mr=a[rt<<1|1].sum+a[rt<<1].mr;
		a[rt].rr=a[rt<<1].rr;
	}

	if(a[rt<<1].Max>=a[rt<<1|1].Max){
		a[rt].Max=a[rt<<1].Max;
		a[rt].l=a[rt<<1].l;a[rt].r=a[rt<<1].r;
	}else {
		a[rt].Max=a[rt<<1|1].Max;
		a[rt].l=a[rt<<1|1].l;a[rt].r=a[rt<<1|1].r;
	}
	if(a[rt].ml>=a[rt].Max){
		a[rt].Max=a[rt].ml;
		a[rt].l=l;a[rt].r=a[rt].ll;
	}
	if(a[rt].mr>a[rt].Max || (a[rt].mr==a[rt].Max && a[rt].l>a[rt].rr)){
		a[rt].Max=a[rt].mr;
		a[rt].l=a[rt].rr;a[rt].r=r;
	}
	int tot=a[rt<<1].mr+a[rt<<1|1].ml;
	if(a[rt].Max<tot || (a[rt].Max==tot && a[rt].l>a[rt<<1].rr) || (a[rt].Max==tot && a[rt].l==a[rt<<1].rr && a[rt].r>a[rt<<1|1].ll)){
		a[rt].Max=tot;
		a[rt].l=a[rt<<1].rr;
		a[rt].r=a[rt<<1|1].ll;
	}
}
void Build(int rt,int l,int r){
	if(l==r){
		LL x;scanf("%lld",&x);
		//printf("%d ",x);
		a[rt]=Node(x);a[rt].l=a[rt].r=a[rt].ll=a[rt].rr=l;
		a[rt].L=l;a[rt].R=r;
		return;
	}
	int mid=(l+r)>>1;
	Build(lson);Build(rson);
	pushup(rt,l,r);
}
void Print(int rt,int l,int r){
	printf("l=%d r=%d ll=%d rr=%d  l=%d r=%d ml=%d mr=%d max=%d sum=%d\n",l,r,a[rt].ll,a[rt].rr,a[rt].l,a[rt].r,a[rt].ml,a[rt].mr,a[rt].Max,a[rt].sum);
	if(l==r)return;
	int mid=(l+r)>>1;
	Print(lson);Print(rson);

}
Node Query(int s,int t,int rt,int l,int r){
	if(s<=l && t>=r){
		//printf("return::");
		//printf("l=%d r=%d ll=%d rr=%d l=%d r=%d ml=%d mr=%d max=%d sum=%d\n",l,r,a[rt].ll,a[rt].rr,a[rt].l,a[rt].r,a[rt].ml,a[rt].mr,a[rt].Max,a[rt].sum);
	
		return a[rt];
	}
	int mid=(l+r)>>1;
	if(t<=mid){
		Node ans=Query(s,t,lson);//printf("left:");
		//printf("l=%d r=%d ll=%d rr=%d l=%d r=%d ml=%d mr=%d max=%d sum=%d\n",l,r,ans.ll,ans.rr,ans.l,ans.r,ans.ml,ans.mr,ans.Max,ans.sum);
		return ans;
	}
	if(s>mid){
		Node ans=Query(s,t,rson);//printf("right:");
		//printf("l=%d r=%d ll=%d rr=%d l=%d r=%d ml=%d mr=%d max=%d sum=%d\n",l,r,ans.ll,ans.rr,ans.l,ans.r,ans.ml,ans.mr,ans.Max,ans.sum);
		return ans;
	}
	Node lc=Query(s,t,lson),rc=Query(s,t,rson);
	Node ans;
	ans.sum=lc.sum+rc.sum;
	ans.L=lc.L;ans.R=rc.R;
	ans.ml=lc.ml;ans.ll=lc.ll;
	if(lc.ml==lc.sum){
		if(ans.ml<lc.ml+rc.ml){
			ans.ml=lc.ml+rc.ml;
			ans.ll=rc.ll;
		}
		//ans.ml=max(ans.ml,lc.ml+rc.ml);
	}
	if(lc.sum+rc.ml>ans.ml){//
		ans.ml=lc.sum+rc.ml;
		ans.ll=rc.ll;
	}

	ans.mr=rc.mr;ans.rr=rc.rr;
	if(rc.mr==rc.sum){
		if(ans.mr<=rc.mr+lc.mr){
			ans.mr=rc.mr+lc.mr;
			ans.rr=lc.rr;
		}
		//ans.mr=max(ans.mr,rc.mr+lc.mr);
	}
	if(rc.sum+lc.mr>ans.mr){//
		ans.mr=rc.sum+lc.mr;
		ans.rr=lc.rr;
	}

	if(lc.Max>=rc.Max){
		ans.Max=lc.Max;
		ans.l=lc.l;ans.r=lc.r;
	}else {
		ans.Max=rc.Max;
		ans.l=rc.l;ans.r=rc.r;
	}//puts("");
	
	//ans.Max=max(lc.Max,rc.Max);
	if(ans.ml>=ans.Max){
		ans.Max=ans.ml;
		ans.l=ans.L;ans.r=ans.ll;
	}//printf("ans::l=%d r=%d L=%d ll=%d rr=%d l=%d r=%d ml=%d mr=%d max=%d sum=%d\n",l,r,ans.L,ans.ll,ans.rr,ans.l,ans.r,ans.ml,ans.mr,ans.Max,ans.sum);
	
	if(ans.mr>ans.Max || (ans.mr==ans.Max && ans.l>ans.rr)){
		ans.Max=ans.mr;
		ans.l=ans.rr;ans.r=ans.R;
	}

	//ans.Max=max(ans.ml,ans.Max);
	//ans.Max=max(ans.mr,ans.Max);
	int tot=lc.mr+rc.ml;
	if(ans.Max<tot || (ans.Max==tot && ans.l>lc.rr) || (ans.Max==tot && ans.l==lc.rr && ans.r>rc.ll)){
		ans.Max=tot;
		ans.l=lc.rr;
		ans.r=rc.ll;
	}
	//printf("merge:\n");
	//printf("lc::l=%d r=%d ll=%d rr=%d l=%d r=%d ml=%d mr=%d max=%d sum=%d\n",l,r,lc.ll,lc.rr,lc.l,lc.r,lc.ml,lc.mr,lc.Max,lc.sum);
	//printf("rt::l=%d r=%d ll=%d rr=%d l=%d r=%d ml=%d mr=%d max=%d sum=%d\n",l,r,rc.ll,rc.rr,rc.l,rc.r,rc.ml,rc.mr,rc.Max,rc.sum);
	//printf("ans::l=%d r=%d ll=%d rr=%d l=%d r=%d ml=%d mr=%d max=%d sum=%d\n",l,r,ans.ll,ans.rr,ans.l,ans.r,ans.ml,ans.mr,ans.Max,ans.sum);
	//puts("\n");
	return ans;
	//ans.Max=max(lc.mr+rc.ml,ans.Max);
	/*ans.sum=lc.sum+rc.sum;
	
	ans.ml=lc.ml;
	if(lc.ml==lc.sum)ans.ml=max(ans.ml,lc.ml+rc.ml);
	
	ans.mr=rc.mr;
	if(rc.mr==rc.sum)ans.mr=max(ans.mr,rc.mr+lc.mr);

	ans.Max=max(lc.Max,rc.Max);
	ans.Max=max(ans.ml,ans.Max);
	ans.Max=max(ans.mr,ans.Max);
	ans.Max=max(lc.mr+rc.ml,ans.Max);
	//printf("merge:\n");
	//printf("lc:: l=%d r=%d ml=%d mr=%d max=%d sum=%d\n",l,r,lc.ml,lc.mr,lc.Max,lc.sum);
	//printf("rc:: l=%d r=%d ml=%d mr=%d max=%d sum=%d\n",l,r,rc.ml,rc.mr,rc.Max,rc.sum);
	//printf("l=%d r=%d ml=%d mr=%d max=%d sum=%d\n",l,r,ans.ml,ans.mr,ans.Max,ans.sum);
	return ans;*/
}
void Init();
int main(){
	 freopen("hill.in","r",stdin);freopen("hill.out","w",stdout);
	Init();
	return 0;
}
void Init(){
	scanf("%d%d",&n,&T);
	Build(1,1,n);//puts("");
	//Print(1,1,n);
	//printf("Max=%d %d %d %d\n",a[1].ml,a[1].mr,a[1].Max,a[1].sum);
	while(T--){
		int s,t;scanf("%d%d",&s,&t);
		Node ans=Query(s,t,1,1,n);
		printf("%d %d %d\n",ans.l,ans.r,ans.Max);
	}
}
/*
1 2
4 6
4 6
1 2
4 6
4 5
1 2
4 6
1 6
4 8
*/
/*
5 1
1 -1 1 -1 2
2 4
 */