记录编号	165319	评测结果	AAAAAAAA
题目名称	山海经	最终得分	100
用户昵称	stdafx.h	是否通过	通过
代码语言	C++	运行时间	0.628 s
提交时间	2015-06-11 06:39:24	内存使用	15.55 MiB

//AUTHOR::STDAFX
//ALGORITHM::LineTree

#define MAX(a,b) ((a)>(b)?(a):(b))

#define lson l,m,t
#define rson m+1,r,t|1

#define MAXN 400010UL

#include <cstdio>

using namespace std;

struct CL{
	int Max;
	int opl,opr;
};


struct Num4{
	CL f,b,m;
	int s;
};

inline int in();
inline void Update(int);
void Build(int,int,int);
Num4 Query(int,int,int);
inline CL CalF(int,CL,CL);
inline CL CalB(int,CL,CL);
inline CL CalM(CL,CL,CL,CL);

int n,m,posl,posr;

Num4 tree[MAXN],tmp;

int main(){
	freopen("hill.in","r",stdin);
	freopen("hill.out","w",stdout);
	scanf("%d%d",&n,&m);
	Build(1,n,1);
	for(int i=1;i<=m;i++){
		posl=in();
		posr=in();
		tmp=Query(1,n,1);
		printf("%d %d %d\n",tmp.m.opl,tmp.m.opr,tmp.m.Max);
	}
	return 0;
}

CL CalM(CL A,CL B,CL C,CL D){
	CL rtn;
	rtn.Max=MAX(MAX(A.Max,B.Max),C.Max+D.Max);
	if(A.Max==rtn.Max){
		return A;
	}
	else if(C.Max+D.Max==rtn.Max){
		rtn.opl=C.opl;
		rtn.opr=D.opr;
		return rtn;
	}
	else{
		return B;
	}
}

CL CalF(int A,CL B,CL C){
	CL rtn;
	rtn.Max=MAX(A+B.Max,C.Max);
	if(rtn.Max==C.Max){
		return C;
	}
	rtn.opl=C.opl;
	rtn.opr=B.opr;
	return rtn;
}

CL CalB(int A,CL B,CL C){
	CL rtn;
	rtn.Max=MAX(A+B.Max,C.Max);
	if(rtn.Max==A+B.Max){
		rtn.opl=B.opl;
		rtn.opr=C.opr;
		return rtn;
	}
	return C;
}

Num4 Query(int l,int r,int rt){
	if(posl<=l&&posr>=r){
		return tree[rt];
	}
	int m=(l+r)>>1,t=rt<<1;
	int tx=t|1;
	if(posl<=m&&posr>m){
		Num4 rtnl=Query(lson);
		Num4 rtnr=Query(rson);
		Num4 temp;
		temp.s=rtnl.s+rtnr.s;
		temp.f=CalF(rtnl.s,rtnr.f,rtnl.f);
		temp.b=CalB(rtnr.s,rtnl.b,rtnr.b);
		temp.m=CalM(rtnl.m,rtnr.m,rtnl.b,rtnr.f);
		return temp;
	}
	else if(posl<=m){
		return Query(lson);
	}
	else if(posr>m){
		return Query(rson);
	}
}

void Build(int l,int r,int rt){
	if(l==r){
		tree[rt].f.Max=in();
		tree[rt].s=tree[rt].f.Max;
		tree[rt].b.Max=tree[rt].f.Max;
		tree[rt].m.Max=tree[rt].f.Max;
		tree[rt].f.opl=l;
		tree[rt].f.opr=l;
		tree[rt].b.opl=l;
		tree[rt].b.opr=l;		
		tree[rt].m.opl=l;
		tree[rt].m.opr=l;
		return;
	}
	int m=(l+r)>>1,t=rt<<1;
	Build(lson);
	Build(rson);
	int tx=t|1;
	tree[rt].s=tree[t].s+tree[tx].s;
	tree[rt].f=CalF(tree[t].s,tree[tx].f,tree[t].f);
	tree[rt].b=CalB(tree[tx].s,tree[t].b,tree[tx].b);
	tree[rt].m=CalM(tree[t].m,tree[tx].m,tree[t].b,tree[tx].f);
	return;
}

inline int in(){
	int temp=0;bool flag=0;char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-') flag=1;
		c=getchar();
	}
	for(;c>='0'&&c<='9';c=getchar()){
		temp=temp*10+c-48;
	}
	if(flag) return -temp;
	return temp;
}