记录编号	434454	评测结果	AAAAAAAA
题目名称	山海经	最终得分	100
用户昵称	~玖湫~	是否通过	通过
代码语言	C++	运行时间	0.483 s
提交时间	2017-08-07 21:29:56	内存使用	11.97 MiB

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
const int M=100000+10;
int n,m;
int val[M];
struct DATE{int l,r,ll,rr,lx,rx,lm,rm,mx,sum;}a[4*M];
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
inline void pushup(int rt){
	int l=rt<<1,r=rt<<1|1;
	a[rt].sum=a[l].sum+a[r].sum;
	if(a[l].lm>=a[l].sum+a[r].lm) {a[rt].lm=a[l].lm; a[rt].rr=a[l].rr;}
	else                          {a[rt].lm=a[l].sum+a[r].lm; a[rt].rr=a[r].rr;}
	if(a[l].rm+a[r].sum>=a[r].rm) {a[rt].rm=a[l].rm+a[r].sum; a[rt].ll=a[l].ll;}
	else                          {a[rt].rm=a[r].rm; a[rt].ll=a[r].ll;}
	if(a[l].mx>=a[r].mx)          {a[rt].mx=a[l].mx; a[rt].lx=a[l].lx; a[rt].rx=a[l].rx;}
	else                          {a[rt].mx=a[r].mx; a[rt].lx=a[r].lx; a[rt].rx=a[r].rx;}
	if(a[l].rm+a[r].lm<a[rt].mx)  return ;
	if(a[l].rm+a[r].lm>a[rt].mx)  {a[rt].mx=a[l].rm+a[r].lm; a[rt].lx=a[l].ll;a[rt].rx=a[r].rr;return ;}
	if(a[rt].lx<a[l].ll)          return ;
	if(a[rt].lx>a[l].ll)          {a[rt].lx=a[l].ll; a[rt].rx=a[r].rr;return ;}
	a[rt].rx=min(a[rt].rx,a[r].rr);
}
void bt(int rt,int l,int r){
	a[rt].l=l,a[rt].r=r;
	if(l==r){a[rt].lm=a[rt].rm=a[rt].sum=a[rt].mx=val[l];a[rt].ll=a[rt].rr=a[rt].lx=a[rt].rx=l;return ;}
	int mid=l+r>>1;
	bt(rt<<1,l,mid);bt(rt<<1|1,mid+1,r);
	pushup(rt);
}
DATE query(int s,int t,int rt){
	int l=a[rt].l,r=a[rt].r;
	if(s<=a[rt].l&&a[rt].r<=t) return a[rt];
	int mid=l+r>>1;
	if(t<=mid) return query(s,t,rt<<1);
	if(s>mid) return query(s,t,rt<<1|1);
	DATE x,y,z;
	x=query(s,t,rt<<1);y=query(s,t,rt<<1|1);
	if(x.lm>=x.sum+y.lm)          {z.lm=x.lm; z.l=x.l; z.rr=x.rr;}
	else                          {z.lm=x.sum+y.lm; z.l=x.l; z.rr=y.rr;}
	if(x.rm+y.sum>=y.rm)          {z.rm=x.rm+y.sum; z.ll=x.ll; z.r=y.r;}
	else                          {z.rm=y.rm; z.ll=y.ll; z.r=y.r;}
	if(x.mx>=y.mx)                {z.mx=x.mx; z.lx=x.lx; z.rx=x.rx;}
	else                          {z.mx=y.mx; z.lx=y.lx; z.rx=y.rx;}
	if(x.rm+y.lm<z.mx)            return z;
	if(x.rm+y.lm>z.mx)            {z.mx=x.rm+y.lm; z.lx=x.ll;z.rx=y.rr;return z;}
	if(z.lx<x.ll)                 return z;
	if(z.lx>x.ll)                 {z.lx=x.ll; z.rx=y.rr;return z;}
	z.rx=min(z.rx,y.rr);
	return z;
}
int DK(){
	freopen("hill.in","r",stdin);
	freopen("hill.out","w",stdout);
	n=read();m=read();
	for(int i=1;i<=n;i++) val[i]=read();
	int aa,bb;bt(1,1,n);
	for(int i=1;i<=m;i++){
		aa=read();bb=read();
		DATE ans=query(aa,bb,1);
		printf("%d %d %d\n",ans.lx,ans.rx,ans.mx);
	}
	return 0;
}
int dk=DK();
int main(){
	;
}