记录编号	38479	评测结果	AAAAAAAA
题目名称	山海经	最终得分	100
用户昵称	Makazeu	是否通过	通过
代码语言	C++	运行时间	1.605 s
提交时间	2012-04-19 18:47:18	内存使用	0.64 MiB

#include <cstdio>
#include <cstdlib>
#include <cstring>
const int MAXN=100001;
int N,M,Num[MAXN];
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));}
class Node
{
public:
	int L,R,mid,sum;
	Node *lchild,*rchild;
	int lmax,rmax,tmax;
	int lpos,rpos,tposx,tposy;
};

void Bing(Node *pnt)
{
	Node *lc=pnt->lchild;
	Node *rc=pnt->rchild;
	pnt->sum=lc->sum+rc->sum;
	pnt->tmax=Max(lc->tmax,rc->tmax,rc->lmax+lc->rmax);
	pnt->lmax=Max(lc->lmax,lc->sum+rc->lmax);
	pnt->rmax=Max(rc->rmax,rc->sum+lc->rmax);
	
	//全局最大區間   依次從左至右
	if(pnt->tmax==lc->tmax) {pnt->tposx=lc->tposx;  pnt->tposy=lc->tposy;}  
	else if(pnt->tmax==rc->lmax+lc->rmax) {pnt->tposx=lc->rpos; pnt->tposy=rc->lpos;}
	else if(pnt->tmax==rc->tmax) {pnt->tposx=rc->tposx;  pnt->tposy=rc->tposy;}
	
	//從左起的區間
	if(pnt->lmax==lc->lmax) pnt->lpos=lc->lpos; else pnt->lpos=rc->lpos;
	//從右起的區間
	if(pnt->rmax==rc->rmax) pnt->rpos=rc->rpos; else pnt->rpos=lc->rpos;
}

void Build(Node *pnt,int l,int r)
{
    pnt->L=l; pnt->R=r; pnt->mid=(l+r)>>1; pnt->sum=0;
	pnt->tmax=0;  pnt->lmax=0;  pnt->rmax=0;
    if(l==r)
	{
		pnt->lchild=NULL;
		pnt->rchild=NULL;
		pnt->sum=Num[l];
		pnt->lmax=Num[l];
		pnt->rmax=Num[l];
		pnt->tmax=Num[l];
		pnt->tposx=l;
		pnt->tposy=l;
		pnt->rpos=l;
		pnt->lpos=l;
		return;
	}
    pnt->lchild=new Node;
    pnt->rchild=new Node;
    Build(pnt->lchild,l,pnt->mid);
    Build(pnt->rchild,pnt->mid+1,r);
	Bing(pnt);
}

Node Find(Node *pnt,int x,int y)
{
	if(x==pnt->L && y==pnt->R)  
	{
		Node ans;
		ans.sum=pnt->sum;
		ans.lmax=pnt->lmax;
		ans.rmax=pnt->rmax;
		ans.tmax=pnt->tmax;
		ans.tposx=pnt->tposx;
		ans.tposy=pnt->tposy;
		ans.lpos=pnt->lpos;
		ans.rpos=pnt->rpos;
		return ans; 
	}
	int mid=pnt->mid;
	if(y<=mid) { Node ans; ans=Find(pnt->lchild,x,y); return ans; }
	if(x>mid)   { Node ans; ans=Find(pnt->rchild,x,y); return ans; }
	Node ans,lc,rc;
	lc=Find(pnt->lchild,x,mid);
	rc=Find(pnt->rchild,mid+1,y);
	
	ans.sum=lc.sum+rc.sum;
	ans.tmax=Max(lc.tmax,rc.tmax,rc.lmax+lc.rmax);
	ans.lmax=Max(lc.lmax,lc.sum+rc.lmax);
	ans.rmax=Max(rc.rmax,rc.sum+lc.rmax);
	
	if(ans.tmax==lc.tmax) {ans.tposx=lc.tposx;  ans.tposy=lc.tposy;}  
	else if(ans.tmax==rc.lmax+lc.rmax) {ans.tposx=lc.rpos; ans.tposy=rc.lpos;}
	else if(ans.tmax==rc.tmax) {ans.tposx=rc.tposx;  ans.tposy=rc.tposy;}
	if(ans.lmax==lc.lmax) ans.lpos=lc.lpos; else ans.lpos=rc.lpos;
	if(ans.rmax==rc.rmax) ans.rpos=rc.rpos; else ans.rpos=lc.rpos;
	return ans;
}

Node *Root;
void init()
{
	Root=new Node;
	scanf("%d %d\n",&N,&M);
	for(int i=1;i<=N;i++) scanf("%d",Num+i);
	Build(Root,1,N); int a,b;
	Node tmp;
	for(int i=1;i<=M;i++)
	{
		scanf("%d %d\n",&a,&b);
		tmp=Find(Root,a,b);
		printf("%d %d %d\n",tmp.tposx,tmp.tposy,tmp.tmax);
	}
}

int main()
{
	freopen("hill.in","r",stdin);
	freopen("hill.out","w",stdout);
	init();
	return 0;
}