记录编号	159023	评测结果	AAAAAAAA
题目名称	山海经	最终得分	100
用户昵称	天一阁	是否通过	通过
代码语言	C++	运行时间	0.815 s
提交时间	2015-04-19 06:33:28	内存使用	28.55 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
#include <set>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <queue>
#include <stack>

using namespace std;

#ifdef WIN32
	#define IMT "%I64d"
#else
	#define IMT "%lld"
#endif

#define MINE

#define N 200010
#define l(x) ch[x][0]
#define r(x) ch[x][1]
#define out(x) cout<<#x<<" = "<<x<<endl;
#define PB(x) push_back(x)
#define MP(x) make_pair(x)

template<class T> inline char qread(T &x){
	static char ch;
	int k=1;
	while(!isdigit(ch=getchar())) if(ch=='-') k=-1;
	x=ch-'0';
	while(isdigit(ch=getchar()))
		x=(x<<1)+(x<<3)+ch-'0';
	x*=k;
	return ch;
}

void file(){
	 freopen("hill.in","r",stdin);
	 #ifdef MINE
	 freopen("hill.out","w",stdout);
	 #endif
}

#define ls(x) tree[x].ls
#define rs(x) tree[x].rs
#define lt(x) tree[x].lt
#define rt(x) tree[x].rt
#define lm(x) tree[x].mlt
#define rm(x) tree[x].mrt
#define sum(x) tree[x].sum
#define ms(x) tree[x].ms

struct node{
	int ls,rs,ms,lt,rt,sum,mlt,mrt;
}tree[N<<2];

int ch[N<<1][2],tot,a[N],n,m,cnt;

void update(int o){
	if(!l(o)) return;
	sum(o)=sum(l(o))+sum(r(o));
	if(ms(l(o))>=ms(r(o))){
		ms(o)=ms(l(o)); lm(o)=lm(l(o));
		rm(o)=rm(l(o));
	}
	else{
		ms(o)=ms(r(o)); lm(o)=lm(r(o));
		rm(o)=rm(r(o));
	}
	if(ls(r(o))+rs(l(o))>ms(o) ||
	ls(r(o))+rs(l(o))==ms(o) && (rm(o)>rt(l(o))
	|| rm(o)==rt(l(o))&&lm(o)>lt(r(o)))){
		ms(o)=ls(r(o))+rs(l(o));
		lm(o)=lt(r(o));
		rm(o)=rt(l(o));
	}
	if(ls(l(o))>=sum(l(o))+ls(r(o))){
		ls(o)=ls(l(o));
		lt(o)=lt(l(o));
	}
	else{
		ls(o)=sum(l(o))+ls(r(o));
		lt(o)=lt(r(o));
	}
	if(rs(r(o))>sum(r(o))+rs(l(o))){
		rs(o)=rs(r(o));
		rt(o)=rt(r(o));
	}
	else{
		rs(o)=sum(r(o))+rs(l(o));
		rt(o)=rt(l(o));
	}
}

int build(int l,int r){
	int x=++tot;
	if(l==r){
		lm(x)=rm(x)=lt(x)=rt(x)=l;
		sum(x)=ls(x)=rs(x)=ms(x)=a[l];
		return x;
	}
	int mid=(l+r)>>1;
	l(x)=build(l,mid); r(x)=build(mid+1,r);
	update(x);
	return x;
}

node ask(int o,int l,int r,int ql,int qr){
	if(ql<=l&&r<=qr) return tree[o];
	int mid=(l+r)>>1,lt,rt;
	if(ql<=mid && mid<qr){
		tree[lt=++tot] = ask(l(o),l,mid,ql,qr);
		tree[rt=++tot] = ask(r(o),mid+1,r,ql,qr);
		l(++tot)=lt;
		r(tot)=rt; update(tot);
		return tree[tot];
	}
	if(ql<=mid) return ask(l(o),l,mid,ql,qr);
	if(mid<qr) return ask(r(o),mid+1,r,ql,qr);
}

int main(){
	file();
	qread(n); qread(m);
	for(int i=1;i<=n;i++) qread(a[i]);
	build(1,n);
	cnt=tot;
	for(int i=1,l,r;i<=m;i++){
		qread(l); qread(r);
		//cout<<l<<' '<<r<<endl;
		tot=cnt;
		node ans=ask(1,1,n,l,r);
		//cout<<"debug\n";
		printf("%d %d %d\n",ans.mrt,ans.mlt,ans.ms);
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}