记录编号	38446	评测结果	AAAAAAAA
题目名称	山海经	最终得分	100
用户昵称	苏轼	是否通过	通过
代码语言	C++	运行时间	4.712 s
提交时间	2012-04-18 22:13:56	内存使用	0.65 MiB

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
int n,m,w[100001];
inline int Max(int a,int b) {return a>b?a:b;} 
inline int Max(int a,int b,int c) {return Max(Max(a,b),Max(b,c));}
struct tree
{
	tree *lchild;
	tree *rchild;
	int l,r,sum;
	int lmax,rmax;
	int lm,rm;
	int zmax,zl,zr;
};

void *build(tree *tmp,int ll,int rr)
{
	tmp->l=ll;
	tmp->r=rr;
	tmp->lchild=NULL;
	tmp->rchild=NULL;
	if (ll==rr)
	{
		tmp->lmax=w[ll];
		tmp->rmax=w[ll];
		tmp->lm=ll;
		tmp->rm=rr;
		tmp->zmax=w[ll];
		tmp->zl=ll;
		tmp->zr=ll;
		tmp->sum=w[ll];
		return tmp;
	}
	if (ll<rr)
	{
		int mid;
		mid=(ll+rr)>>1;
		tmp->lchild=new tree;
		tmp->rchild=new tree;
		build(tmp->lchild,ll,mid);
		build(tmp->rchild,mid+1,rr);
		tree *lc=new tree;
		tree *rc=new tree;
		lc=tmp->lchild;
		rc=tmp->rchild;
		
		tmp->sum=lc->sum+rc->sum;
		tmp->zmax=Max(lc->zmax,rc->zmax,rc->lmax+lc->rmax);
		tmp->lmax=Max(lc->lmax,lc->sum+rc->lmax);
		tmp->rmax=Max(rc->rmax,rc->sum+lc->rmax);
		if(tmp->zmax==lc->zmax) {tmp->zl=lc->zl;  tmp->zr=lc->zr;}  
		else if(tmp->zmax==rc->lmax+lc->rmax) {tmp->zl=lc->rm; tmp->zr=rc->lm;}
		else if(tmp->zmax==rc->zmax) {tmp->zl=rc->zl;  tmp->zr=rc->zr;}
		
		if(tmp->lmax==lc->lmax) tmp->lm=lc->lm; else tmp->lm=rc->lm;
		if(tmp->rmax==rc->rmax) tmp->rm=rc->rm; else tmp->rm=lc->rm;
		tmp->sum=lc->sum+rc->sum;
	}
}

tree work(tree *tmp,int ll,int rr)
{
	if (tmp->l==ll&&tmp->r==rr)
	{
		tree ans;
		ans.sum=tmp->sum;
		ans.lmax=tmp->lmax;
		ans.rmax=tmp->rmax;
		ans.zmax=tmp->zmax;
		ans.zl=tmp->zl;
		ans.zr=tmp->zr;
		ans.lm=tmp->lm;
		ans.rm=tmp->rm;
		return ans;
	}
	tree ans;
	int mid;
	mid=(tmp->l+tmp->r)>>1;
	if (rr<=mid)
	{
		ans=work(tmp->lchild,ll,rr);
		return ans;
	}
	if (ll>mid)
	{
		ans=work(tmp->rchild,ll,rr);
		return ans;
	}
	tree lmid,rmid;
	lmid=work(tmp->lchild,ll,mid);
	rmid=work(tmp->rchild,mid+1,rr);
	ans.sum=lmid.sum+rmid.sum;
	ans.zmax=Max(lmid.zmax,rmid.zmax,rmid.lmax+lmid.rmax);
	ans.lmax=Max(lmid.lmax,lmid.sum+rmid.lmax);
	ans.rmax=Max(rmid.rmax,rmid.sum+lmid.rmax);
	
	if(ans.zmax==lmid.zmax) {ans.zl=lmid.zl;  ans.zr=lmid.zr;}  
	else if(ans.zmax==rmid.lmax+lmid.rmax) {ans.zl=lmid.rm; ans.zr=rmid.lm;}
	else if(ans.zmax==rmid.zmax) {ans.zl=rmid.zl;  ans.zr=rmid.zr;}
	if(ans.lmax==lmid.lmax) ans.lm=lmid.lm; else ans.lm=rmid.lm;
	if(ans.rmax==rmid.rmax) ans.rm=rmid.rm; else ans.rm=lmid.rm;
	return ans;
}
int main()
{
	freopen ("hill.in","r",stdin);
	freopen ("hill.out","w",stdout);
	cin>>n>>m;
	for (int i=1;i<=n;i++)
		cin>>w[i];
	tree *root=new tree;
	build(root,1,n);
	tree ans;
	for (int i=0;i<m;i++)
	{
		int a,b;
		cin>>a>>b;
		ans=work(root,a,b);
		cout<<ans.zl<<' '<<ans.zr<<' '<<ans.zmax<<endl;
	}
	return 0;
}