记录编号	433274	评测结果	AAAAAAAA
题目名称	山海经	最终得分	100
用户昵称	A_LEAF	是否通过	通过
代码语言	C++	运行时间	0.776 s
提交时间	2017-08-05 09:36:10	内存使用	19.77 MiB

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int N=100006;
const int INF=0x7fffffff/3;
int maxn(int a,int b){return a>b?a:b;}

int n,m;
int v[N];

struct son
{
	int lval,rval,val,sum;
	int l1,l2,l3,r1,r2,r3;
};
son a[N*5];

void pushup(int x)
{
	int lson=x<<1,rson=x<<1|1;
	if(a[lson].lval>=a[lson].sum+a[rson].lval)
	{
		a[x].lval=a[lson].lval;
		a[x].l1=a[lson].l1;
		a[x].r1=a[lson].r1;
	}
	else
	{
		a[x].lval=a[lson].sum+a[rson].lval;
		a[x].l1=a[lson].l1;
		a[x].r1=a[rson].r1;
	}
	
	if(a[rson].sum+a[lson].rval>=a[rson].rval)
	{
		a[x].rval=a[rson].sum+a[lson].rval;
		a[x].l2=a[lson].l2;
		a[x].r2=a[rson].r2;
	}
	else
	{
		a[x].rval=a[rson].rval;
		a[x].l2=a[rson].l2;
		a[x].r2=a[rson].r2;
	}
	
	int temp=a[lson].rval+a[rson].lval;
	int maxl=maxn(maxn(a[lson].val,a[rson].val),temp);
	a[x].val=maxl;
	if(maxl==a[lson].val)
	{
		a[x].l3=a[lson].l3;
		a[x].r3=a[lson].r3;
	}
	else
	  if(maxl==temp)
	  {
			a[x].l3=a[lson].l2;
			a[x].r3=a[rson].r1;
		}
	else
	{
		a[x].l3=a[rson].l3;
		a[x].r3=a[rson].r3;
	}
	
	a[x].sum=a[lson].sum+a[rson].sum;
}

void build(int l,int r,int x)
{
	if(l==r)
	{
		a[x].lval=a[x].rval=a[x].val=a[x].sum=v[l];
		a[x].l1=a[x].l2=a[x].l3=a[x].r1=a[x].r2=a[x].r3=l;
		return ;
	}
	int mid=(l+r)>>1;
	build(l,mid,x<<1);
	build(mid+1,r,x<<1|1);
	pushup(x);
}

son qq(int L,int R,int l,int r,int x)
{
	if(L<=l&&r<=R)
	  return a[x];
	int mid=(l+r)>>1;
	son ans,lson,rson;
	if(L<=mid)
	  lson=qq(L,R,l,mid,x<<1);
	if(mid<R)
	  rson=qq(L,R,mid+1,r,x<<1|1);
	
	if(L<=mid&&mid<R)
	{
		if(lson.lval>=lson.sum+rson.lval)
		{
			ans.lval=lson.lval;
			ans.l1=lson.l1;
			ans.r1=lson.r1;
		}
		else
		{
			ans.lval=lson.sum+rson.lval;
			ans.l1=lson.l1;
			ans.r1=rson.r1;
		}
		
		if(rson.sum+lson.rval>=rson.rval)
		{
			ans.rval=rson.sum+lson.rval;
			ans.l2=lson.l2;
			ans.r2=rson.r2;
		}
		else
		{
			ans.rval=rson.rval;
			ans.l2=rson.l2;
			ans.r2=rson.r2;
		}
		
		int temp=lson.rval+rson.lval;
		int maxl=maxn(maxn(lson.val,rson.val),temp);
		ans.val=maxl;
		if(maxl==lson.val)
		{
			ans.l3=lson.l3;
			ans.r3=lson.r3;
		}
		else
		  if(maxl==temp)
		  {
				ans.l3=lson.l2;
				ans.r3=rson.r1;
			}
		else
		{
			ans.l3=rson.l3;
			ans.r3=rson.r3;
		}
		
		ans.sum=lson.sum+rson.sum;
	}
	else
	  if(L<=mid)
	    ans=lson;
	else
	  ans=rson;
	return ans;
}

int main(){
	freopen("hill.in","r",stdin);
	freopen("hill.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i)
	  scanf("%d",&v[i]);
	
	build(1,n,1);
	
	while(m--)
	{
		int aa,bb;
		scanf("%d%d",&aa,&bb);
		son temp=qq(aa,bb,1,n,1);
		int maxl=maxn(maxn(temp.lval,temp.rval),temp.val);
		if(maxl==temp.lval)
			printf("%d %d %d\n",temp.l1,temp.r1,maxl);
		else
		  if(maxl==temp.val)
		    printf("%d %d %d\n",temp.l3,temp.r3,maxl);
		else
		  printf("%d %d %d\n",temp.l2,temp.r2,maxl);
	}
	//while(1);
	return 0;
}