记录编号	237579	评测结果	AAAAAAAA
题目名称	山海经	最终得分	100
用户昵称	zys	是否通过	通过
代码语言	C++	运行时间	1.262 s
提交时间	2016-03-17 18:48:21	内存使用	0.30 MiB

#define null NULL
#define inf 0x3fffffff
#define L(rt) rt->left
#define R(rt) rt->right
#define lson l,mid,rt->left
#define rson mid+1,r,rt->right

#include<cstdio>

using namespace std;

inline int read()
{
	int x=0;char c=getchar();bool flag=0;
	while(c<48||c>57){if(c==45)flag=1;c=getchar();}
	for(;c>47&&c<58;c=getchar())x=(x<<3)+(x<<1)+c-48;
	if(flag)return -x;
	return x;
}

int n,m,posl,posr;bool flag;

struct Seg_tree{
	Seg_tree *left,*right;
	int lmax,rmax,vmax,lid[3],rid[3],sum;
	Seg_tree(){left=right=null;sum=lmax=rmax=vmax=-inf;}
}*root,*ans;

void bind(Seg_tree *&ret,Seg_tree *p)
{
	ret->lid[0]=p->lid[0];ret->lid[1]=p->lid[1];ret->lid[2]=p->lid[2];
	ret->rid[0]=p->rid[0];ret->rid[1]=p->rid[1];ret->rid[2]=p->rid[2];
	ret->lmax=p->lmax;ret->rmax=p->rmax;ret->vmax=p->vmax;ret->sum=p->sum;
}

void plus(Seg_tree *ls,Seg_tree *rs,Seg_tree *&ret)
{
	Seg_tree *l=new Seg_tree(),*r=new Seg_tree();
	bind(l,ls);bind(r,rs);
	ret->sum=l->sum+r->sum;ret->lid[0]=l->lid[0];ret->rid[0]=r->rid[0];
	if(l->lmax>=l->sum+r->lmax)ret->lmax=l->lmax,ret->lid[1]=l->lid[1];
	else ret->lmax=l->sum+r->lmax,ret->lid[1]=r->lid[1];
	if(l->rmax+r->sum>=r->rmax)ret->rmax=l->rmax+r->sum,ret->rid[1]=l->rid[1];
	else ret->rmax=r->rmax,ret->rid[1]=r->rid[1];
	if(l->vmax>=l->rmax+r->lmax)ret->vmax=l->vmax,ret->lid[2]=l->lid[2],ret->rid[2]=l->rid[2];
	else ret->vmax=l->rmax+r->lmax,ret->lid[2]=l->rid[1],ret->rid[2]=r->lid[1];
	if(r->vmax>ret->vmax)ret->vmax=r->vmax,ret->lid[2]=r->lid[2],ret->rid[2]=r->rid[2];
	if(ret->lmax>ret->vmax)ret->vmax=ret->lmax,ret->lid[2]=ret->lid[0],ret->rid[2]=ret->lid[1];
	else if(ret->lmax==ret->vmax&&(ret->lid[0]<ret->lid[2]||(ret->lid[0]==ret->lid[2]&&ret->lid[1]<ret->rid[2])))
	    ret->vmax=ret->lmax,ret->lid[2]=ret->lid[0],ret->rid[2]=ret->lid[1];
	if(ret->rmax>ret->vmax)ret->vmax=ret->rmax,ret->lid[2]=ret->rid[1],ret->rid[2]=ret->rid[0];
	else if(ret->rmax==ret->vmax&&(ret->rid[1]<ret->lid[2]||(ret->rid[1]==ret->lid[2]&&ret->rid[0]<ret->rid[2])))
	    ret->vmax=ret->rmax,ret->lid[2]=ret->rid[1],ret->rid[2]=ret->rid[0];
	delete l;delete r;
}
	
void build(int l,int r,Seg_tree *&rt)
{
	if(rt==null)rt=new Seg_tree();
	if(l==r){
		rt->lid[0]=l;rt->rid[0]=r;
		rt->lid[1]=rt->lid[2]=rt->rid[1]=rt->rid[2]=l;
		rt->vmax=read();rt->lmax=rt->rmax=rt->sum=rt->vmax;return;
	}
	int mid=(l+r)>>1;build(lson);build(rson);
	plus(L(rt),R(rt),rt);
}

void query(int l,int r,Seg_tree *rt)
{
	if(posl<=l&&posr>=r){
		if(!flag)bind(ans,rt),flag=1;
		else plus(ans,rt,ans);return;
	}
	int mid=(l+r)>>1;
	if(posl<=mid)query(lson);
	if(posr>mid)query(rson);
}

int main()
{
    freopen("hill.in","r",stdin);
	freopen("hill.out","w",stdout);
	n=read();m=read();
	build(1,n,root);ans=new Seg_tree();
	for(int i=1;i<=m;i++){
		posl=read();posr=read();
		ans->sum=ans->lmax=ans->rmax=ans->vmax=-inf;
		flag=0;query(1,n,root);
		printf("%d %d %d\n",ans->lid[2],ans->rid[2],ans->vmax);
	}
}