记录编号	159554	评测结果	AAAAAAAA
题目名称	山海经	最终得分	100
用户昵称	ggwdwsbs	是否通过	通过
代码语言	C++	运行时间	1.143 s
提交时间	2015-04-21 20:21:04	内存使用	22.04 MiB

#include<stdio.h>
#include<cstring>
const int maxn=100010;
const int INF=2147483600;
struct qj
{
	int l,r,w;
};
struct tree
{
	int left,right;
	qj sum,smx,lmx,rmx;
}a[maxn*4];
int b[maxn];
int n,m,l,r;
tree zero=(tree){0,0,{INF,INF,0},{INF,INF,0},{INF,INF,0},{INF,INF,0}};
bool empty(qj a)
{
	return a.l==INF;
}
inline qj operator + (qj a,qj b)
{
	if(empty(b)) return a;
	if(empty(a)) return b;
	qj c;
	c.l=a.l;
	c.r=b.r;
	c.w=b.w+a.w;
	return c;
}
inline bool operator > (qj a,qj b)
{
	if(a.w!=b.w) return a.w>b.w;
	if(a.l!=b.l) return a.l<b.l;
	else return a.r<b.r;
}
qj max(qj x,qj y)
{
	if(x>y) return x;
	else return y;
}
inline tree operator + (tree a,tree b)
{
	if(empty(b.sum)) return a;
	if(empty(a.sum)) return b;
	tree c;
	c.sum=a.sum+b.sum;
	c.lmx=max(a.lmx,a.sum+b.lmx);
	c.rmx=max(b.rmx,a.rmx+b.sum);
	c.smx=max(a.smx,b.smx);
	if(!empty(a.rmx)||!empty(b.lmx))
	 c.smx=max(c.smx,a.rmx+b.lmx);
	return c;
}

int give(int k,int l)
{
	qj c;
	c.l=c.r=l;
	c.w=b[l];
	a[k].sum=c;
	a[k].smx=c;
	if(c.w>0) a[k].lmx=c;
	else a[k].lmx=zero.sum;
	if(c.w>=0) a[k].rmx=c;
	else a[k].rmx=zero.sum;
}

int build(int k,int l,int r)
{
	if(l==r) give(k,l);
	else
	{
		build(2*k,l,(l+r)/2);
		build(2*k+1,(l+r)/2+1,r);
		a[k]=a[2*k]+a[2*k+1];
	}
	a[k].left=l;
	a[k].right=r;
}
tree query(int k,int l,int r)
{
	if(l>a[k].right||a[k].left>r) return zero;
	if(l<=a[k].left&&a[k].right<=r) return a[k];
	return query(2*k,l,r)+query(2*k+1,l,r);
}
int main()
{
	freopen("hill.in","r",stdin);
	freopen("hill.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&b[i]);
	build(1,1,n);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&l,&r);
		tree c=query(1,l,r);
		printf("%d %d %d\n",c.smx.l,c.smx.r,c.smx.w);
	}
}