记录编号	299081	评测结果	AAAAAAAA
题目名称	山海经	最终得分	100
用户昵称	dateri	是否通过	通过
代码语言	C++	运行时间	0.849 s
提交时间	2016-08-24 01:05:41	内存使用	11.63 MiB

#include<cstdio>
#define max(a,b) ((a)>(b)?(a):(b))
using namespace std;
struct ww{
	int l_,r_,va;
};
struct ff{
   ww _l,_r,maxnum,sum;
};
const int N=100005;
bool flag,fu;
ff tree[N<<2],ex,temp;
inline void in(int &n)
{
	fu=false,n=0;
	char c;
	c=getchar();
	if(c=='-') fu=true;
	while(c>'9'||c<'0')
	{
	  c=getchar();
	  if(c=='-') fu=true;
	}
	do
	  n=(n<<3)+(n<<1)+c-'0',c=getchar();
	while(c>='0'&&c<='9');
	if(fu) n=-n;
}
void build(int l,int r,int rt)
{
	if(l==r)
	{
		in(tree[rt].sum.va);
		tree[rt]._l.va=tree[rt]._r.va=tree[rt].maxnum.va=tree[rt].sum.va;
		tree[rt]._l.l_=tree[rt]._l.r_=tree[rt]._r.l_=tree[rt]._r.r_=tree[rt].maxnum.l_=tree[rt].maxnum.r_=tree[rt].sum.l_=tree[rt].sum.r_=l;
		return ;
	}
	int m=l+r>>1;
	build(l,m,rt<<1);
	build(m+1,r,rt<<1|1);
	tree[rt].sum.va=tree[rt<<1].sum.va+tree[rt<<1|1].sum.va,tree[rt].sum.l_=tree[rt<<1].sum.l_,tree[rt].sum.r_=tree[rt<<1|1].sum.r_;
	if(tree[rt<<1]._l.va>=tree[rt<<1].sum.va+tree[rt<<1|1]._l.va)
	  tree[rt]._l=tree[rt<<1]._l;
	else
	  tree[rt]._l.va=tree[rt<<1].sum.va+tree[rt<<1|1]._l.va,tree[rt]._l.l_=tree[rt<<1]._l.l_,tree[rt]._l.r_=tree[rt<<1|1]._l.r_;
	if(tree[rt<<1|1].sum.va+tree[rt<<1]._r.va>=tree[rt<<1|1]._r.va)
	  tree[rt]._r.va=tree[rt<<1|1].sum.va+tree[rt<<1]._r.va,tree[rt]._r.l_=tree[rt<<1]._r.l_,tree[rt]._r.r_=tree[rt<<1|1]._r.r_;
	else
	  tree[rt]._r=tree[rt<<1|1]._r;
	if(tree[rt<<1].maxnum.va>=tree[rt<<1]._r.va+tree[rt<<1|1]._l.va&&tree[rt<<1].maxnum.va>=tree[rt<<1|1].maxnum.va)
	  tree[rt].maxnum=tree[rt<<1].maxnum;
	else if(tree[rt<<1]._r.va+tree[rt<<1|1]._l.va>=tree[rt<<1].maxnum.va&&tree[rt<<1]._r.va+tree[rt<<1|1]._l.va>=tree[rt<<1|1].maxnum.va)
	  tree[rt].maxnum.va=tree[rt<<1]._r.va+tree[rt<<1|1]._l.va,tree[rt].maxnum.l_=tree[rt<<1]._r.l_,tree[rt].maxnum.r_=tree[rt<<1|1]._l.r_;
	else
	  tree[rt].maxnum=tree[rt<<1|1].maxnum;
}
void query(int L,int R,int l,int r,int rt)
{
	if(l>=L&&r<=R)
	{
		if(flag==false)
		  ex=tree[rt],flag=true;
		else
		{
			temp=ex;
		  	ex.sum.va=temp.sum.va+tree[rt].sum.va,ex.sum.l_=temp.sum.l_,ex.sum.r_=tree[rt].sum.r_;
		  	if(temp._l.va<temp.sum.va+tree[rt]._l.va)
	          ex._l.va=temp.sum.va+tree[rt]._l.va,temp._l.r_=tree[rt]._l.r_;
		  	if(tree[rt]._r.va<=tree[rt].sum.va+temp._r.va)
	          ex._r.va=tree[rt].sum.va+temp._r.va,ex._r.r_=tree[rt]._r.r_;
	        else
	          ex._r=tree[rt]._r;
	        if(temp.maxnum.va>=temp._r.va+tree[rt]._l.va&&temp.maxnum.va>=tree[rt].maxnum.va)
			  ;
	        else if(temp._r.va+tree[rt]._l.va>=temp.maxnum.va&&temp._r.va+tree[rt]._l.va>=tree[rt].maxnum.va)
	          ex.maxnum.va=temp._r.va+tree[rt]._l.va,ex.maxnum.l_=temp._r.l_,ex.maxnum.r_=tree[rt]._l.r_;
	        else
	          ex.maxnum=tree[rt].maxnum;
		}
		return ;
	}
	int m=l+r>>1;
	if(m>=L) query(L,R,l,m,rt<<1);
	if(m+1<=R) query(L,R,m+1,r,rt<<1|1);
}
int cc()
{
    freopen("hill.in","r",stdin);
	freopen("hill.out","w",stdout);
	int n,m,a,b;
	in(n),in(m);
	build(1,n,1);
	while(m--)
	{
	  in(a),in(b);
	  flag=false,query(a,b,1,n,1);
	  printf("%d %d %d\n",ex.maxnum.l_,ex.maxnum.r_,ex.maxnum.va);
	}
	return 0;
}
int ccc=cc();
int main(){;}