记录编号	427996	评测结果	AAAAAAAA
题目名称	山海经	最终得分	100
用户昵称	Anonymity	是否通过	通过
代码语言	C++	运行时间	1.013 s
提交时间	2017-07-24 10:40:39	内存使用	15.55 MiB

#include<cstdio>
#define maxn 400005
using namespace std;
int n,m,inf=0xfffffff;
struct tree{int lc,rc,sum,lmax,rmax,ma,lpos,rpos,ml,mr;tree(){lmax=rmax=ma=-inf;sum=0;}}tr[maxn];
void pushup(int x)
{
	int lch=x<<1,rch=lch|1;
	tr[x].sum=tr[lch].sum+tr[rch].sum;
	if(tr[lch].lmax<tr[lch].sum+tr[rch].lmax) tr[x].lmax=tr[lch].sum+tr[rch].lmax,tr[x].lpos=tr[rch].lpos;
	else tr[x].lmax=tr[lch].lmax,tr[x].lpos=tr[lch].lpos;
	if(tr[rch].rmax<tr[rch].sum+tr[lch].rmax) tr[x].rmax=tr[rch].sum+tr[lch].rmax,tr[x].rpos=tr[lch].rpos;
	else tr[x].rmax=tr[rch].rmax,tr[x].rpos=tr[rch].rpos;
	if(tr[lch].ma<tr[rch].ma)
	{
		if(tr[rch].ma<=tr[lch].rmax+tr[rch].lmax) tr[x].ma=tr[lch].rmax+tr[rch].lmax,tr[x].ml=tr[lch].rpos,tr[x].mr=tr[rch].lpos;
		else tr[x].ma=tr[rch].ma,tr[x].ml=tr[rch].ml,tr[x].mr=tr[rch].mr;
	}
	else if(tr[lch].ma<tr[lch].rmax+tr[rch].lmax) tr[x].ma=tr[lch].rmax+tr[rch].lmax,tr[x].ml=tr[lch].rpos,tr[x].mr=tr[rch].lpos;
	else if(tr[lch].ma==tr[lch].rmax+tr[rch].lmax)
		 {	 tr[x].ma=tr[lch].ma;
			 if(tr[lch].rpos<tr[lch].ml) tr[x].ml=tr[lch].rpos,tr[x].mr=tr[rch].lpos;
			 else tr[x].ml=tr[lch].ml,tr[x].mr=tr[lch].mr;
		 }
	else tr[x].ma=tr[lch].ma,tr[x].ml=tr[lch].ml,tr[x].mr=tr[lch].mr;
}
void cmp(tree x,tree y,tree &z)
{
	z.lc=x.lc;z.rc=y.rc;
	z.sum=x.sum+y.sum;
	if(x.lmax<x.sum+y.lmax) z.lmax=x.sum+y.lmax,z.lpos=y.lpos;
	else z.lmax=x.lmax,z.lpos=x.lpos;
	if(y.rmax<y.sum+x.rmax) z.rmax=y.sum+x.rmax,z.rpos=x.rpos;
	else z.rmax=y.rmax,z.rpos=y.rpos;
	if(x.ma<y.ma)
	{
		if(y.ma<=x.rmax+y.lmax) z.ma=x.rmax+y.lmax,z.ml=x.rpos,z.mr=y.lpos;
		else z.ma=y.ma,z.ml=y.ml,z.mr=y.mr;
	}
	else if(x.ma<x.rmax+y.lmax) z.ma=x.rmax+y.lmax,z.ml=x.rpos,z.mr=y.lpos;
	else if(x.ma==x.rmax+y.lmax)
		 {	 z.ma=x.ma;
			 if(x.rpos<x.ml) z.ml=x.rpos,z.mr=y.lpos;
			 else z.ml=x.ml,z.mr=x.mr;
		 }
	else z.ma=x.ma,z.ml=x.ml,z.mr=x.mr;
}
void build(int x,int y,int z)
{
	tr[z].lc=x;tr[z].rc=y;
	if(x==y)
	{
		int tmp;scanf("%d",&tmp);
		tr[z].sum=tr[z].lmax=tr[z].rmax=tr[z].ma=tmp;
		tr[z].lpos=tr[z].rpos=tr[z].ml=tr[z].mr=x;
		return;
	}
	int mid=x+y>>1,lch=z<<1,rch=lch|1;
	build(x,mid,lch);build(mid+1,y,rch);
	pushup(z);
}
tree query(int x,int y,int z)
{
	if(tr[z].lc>=x&&tr[z].rc<=y)
		return tr[z];
	int mid=tr[z].lc+tr[z].rc>>1,lch=z<<1,rch=lch|1;tree t1,t2,t3;
	if(x<=mid) t1=query(x,y,lch);
	if(mid<y) t2=query(x,y,rch);
	t1.lc=x;t1.rc=mid;t2.lc=mid+1;t2.rc=y;
	cmp(t1,t2,t3);
	return t3;
}
void print(tree x)
{
	if(x.lmax>=x.rmax)
	{
		if(x.lmax>=x.ma) printf("%d %d %d\n",x.lc,x.lpos,x.lmax);
		else printf("%d %d %d\n",x.ml,x.mr,x.ma);
	}
	else if(x.rmax>x.ma) printf("%d %d %d\n",x.rpos,x.rc,x.rmax);
	else printf("%d %d %d\n",x.ml,x.mr,x.ma);
}
int main()
{
	freopen("hill.in","r",stdin);
	freopen("hill.out","w",stdout);
	scanf("%d%d",&n,&m);
	build(1,n,1);int x,y;
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		tree tmp=query(x,y,1);
		print(tmp);
	}
	return 0;
}