记录编号	283818	评测结果	AAAAAAAA
题目名称	山海经	最终得分	100
用户昵称	0	是否通过	通过
代码语言	C++	运行时间	0.483 s
提交时间	2016-07-15 17:53:12	内存使用	13.95 MiB

#include<cstdio>

#define MAX(a,b) ((a)>(b)?(a):(b))
#define INF -0x7fffffff
 
using namespace std;
 
int n,m;
bool flag=0;
 
struct st{
	int w,l,r;
};
 
struct at{
	st l,r,s,m;
}tr[400010],temp;
 
inline void in(int & a)
{
	bool flag=0;
	a=0;
	char c;
	c=getchar();
	while(c<'0'||c>'9')
	{
		if(c=='-')
			flag=1;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		a=a*10+c-'0';
		c=getchar();		
	}
	if(flag)
		a=-a;
	return;
}
 
bool PD(st a,st b)
{
	if(a.w==b.w)
	{
		if(a.l<b.l)
			return 1;
		if(a.r<b.r)
			return 1;
	}
	return 0;
}
 
void query(int al,int ar,int l,int r,int n)
{
	if(al<=l&&r<=ar)
	{
		if(!flag)
		{
			flag=1;
			temp=tr[n];
			return;
		}	
		if(tr[n].m.w>temp.m.w||PD(tr[n].m,temp.m))
		{
			temp.m=tr[n].m;
		}
		st a;
		a.l=temp.r.l;
		a.r=tr[n].l.r;
		a.w=temp.r.w+tr[n].l.w;
		if(temp.r.w+tr[n].l.w>temp.m.w||PD(a,temp.m))
		{
			temp.m.w=temp.r.w+tr[n].l.w;
			temp.m.l=temp.r.l;
			temp.m.r=tr[n].l.r;
		}
		if(tr[n].r.w>tr[n].s.w+temp.r.w)
		{
			temp.r=tr[n].r;
		}
		else
		{
			temp.r.w=tr[n].s.w+temp.r.w;
			temp.r.l=temp.r.l;
			temp.r.r=tr[n].r.r;
		}
		temp.s.w+=tr[n].s.w;
		return;
	}
	int m=(l+r)>>1;
	if(m>=al)
		query(al,ar,l,m,n<<1);
	if(m<ar)
		query(al,ar,m+1,r,n<<1|1);
	return;
}
 
void build(int l,int r,int n)
{
	if(l==r)
	{
		in(tr[n].m.w);
		tr[n].s.w=tr[n].l.w=tr[n].r.w=tr[n].m.w;
		tr[n].l.l=l;
		tr[n].l.r=l;
		tr[n].r.l=l;
		tr[n].r.r=l;
		tr[n].m.l=l;
		tr[n].m.r=l;
		return;
	}
	int m=(l+r)>>1;
	build(l,m,n<<1);
	build(m+1,r,n<<1|1);
/*======================最左端====================*/
	if(tr[n<<1].l.w>=tr[n<<1].s.w+tr[n<<1|1].l.w)
	{	
		tr[n].l=tr[n<<1].l;
	}
	else
	{	
		tr[n].l.w=tr[n<<1].s.w+tr[n<<1|1].l.w;
		tr[n].l.l=tr[n<<1].l.l;
		tr[n].l.r=tr[n<<1|1].l.r;
	}
/*======================最右端=====================*/
	if(tr[n<<1|1].r.w>tr[n<<1].r.w+tr[n<<1|1].s.w)
	{
		tr[n].r=tr[n<<1|1].r;
	}
	else
	{
		tr[n].r.w=tr[n<<1].r.w+tr[n<<1|1].s.w;
		tr[n].r.l=tr[n<<1].r.l;
		tr[n].r.r=tr[n<<1|1].r.r;
	}
/*=====================区间和======================*/
	tr[n].s.w=tr[n<<1].s.w+tr[n<<1|1].s.w;
/*====================区间最大值===================*/ 
	if(tr[n<<1].m.w>=tr[n<<1|1].m.w)
	{
		tr[n].m=tr[n<<1].m;
	}
	else
	{
		tr[n].m=tr[n<<1|1].m;
	}
	st a;
	a.l=tr[n<<1].r.l;
	a.r=tr[n<<1|1].l.r;
	a.w=tr[n<<1].r.w+tr[n<<1|1].l.w;
	if(a.w>tr[n].m.w||PD(a,tr[n].m))
	{
		tr[n].m.w=tr[n<<1].r.w+tr[n<<1|1].l.w;
		tr[n].m.l=tr[n<<1].r.l;
		tr[n].m.r=tr[n<<1|1].l.r;
	}
	return;
}
 
bool work()
{
	freopen("hill.in","r",stdin);
	freopen("hill.out","w",stdout);
	in(n);
	in(m);
	build(1,n,1);
	/*for(int i=1;i<=n*3;i++)
	{
		printf("%d %d %d\n",tr[i].m.l,tr[i].m.r,tr[i].m.w);
	}*/
	for(int i=1;i<=m;i++)
	{
		int x,y;
		in(x);
		in(y);
		flag=0;
		query(x,y,1,n,1);
		printf("%d %d %d\n",temp.m.l,temp.m.r,temp.m.w);
	}
	return 0;
}

bool tmp=work();
main(){;}