记录编号	237452	评测结果	AAAAAAAA
题目名称	山海经	最终得分	100
用户昵称	葳棠殇	是否通过	通过
代码语言	C++	运行时间	0.781 s
提交时间	2016-03-17 15:20:15	内存使用	22.42 MiB

#include<ctype.h>
#include<stdio.h>
using namespace std;
struct data{
	long long sum,mx,lmx,rmx;
	int l,r,llpos,rrpos,lpos,rpos;
	void init(long long x,int ll){
		sum=lmx=rmx=mx=x;
		l=r=llpos=lpos=rpos=rrpos=ll;
	}
	friend data operator + (data a,data b){
		data c;
		c.sum=a.sum+b.sum,c.l=a.l,c.r=b.r,c.lmx=a.lmx,c.lpos=a.lpos;
		if(c.lmx<a.sum+b.lmx)c.lmx=a.sum+b.lmx,c.lpos=b.lpos;
		c.rmx=b.rmx,c.rpos=b.rpos;
		if(c.rmx<=a.rmx+b.sum)c.rmx=a.rmx+b.sum,c.rpos=a.rpos;
		c.mx=a.mx,c.llpos=a.llpos,c.rrpos=a.rrpos;
		if(c.mx<a.rmx+b.lmx)c.mx=a.rmx+b.lmx,c.llpos=a.rpos,c.rrpos=b.lpos;
		if(c.mx<b.mx)c.mx=b.mx,c.llpos=b.llpos,c.rrpos=b.rrpos;
		return c;
	}
}node[400050];
long long a[100005],n,m,l,r;
char ch;bool flag;
void build(int l,int r,int rt){
	if(l==r){
		node[rt].init(a[l],l);
		return;
	}
	int mid=l+r>>1;
	build(l,mid,rt<<1),build(mid+1,r,rt<<1|1),node[rt]=node[rt<<1]+node[rt<<1|1];
}
data Getans(int ll,int rr,int l,int r,int rt){
	if(l==ll&&r==rr)return node[rt];
	int mid=l+r>>1;
	if(ll>mid)return Getans(ll,rr,mid+1,r,rt<<1|1);
	if(rr<=mid)return Getans(ll,rr,l,mid,rt<<1);
	return Getans(ll,mid,l,mid,rt<<1)+Getans(mid+1,rr,mid+1,r,rt<<1|1);
}
void IN(long long &x){
	ch=getchar();flag=true;
	while(!isdigit(ch)){if(ch=='-')flag=false;ch=getchar();}
	x=ch^48;ch=getchar();while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(!flag)x=-x;
}
int main(){
	freopen("hill.in","r",stdin);
	freopen("hill.out","w",stdout);
	IN(n),IN(m);
	for(int i=1;i<=n;i++)IN(a[i]);
	build(1,n,1);
	while(m--){
		IN(l),IN(r);
		data ans=Getans(l,r,1,n,1);
		printf("%d %d %d\n",ans.llpos,ans.rrpos,ans.mx);
	}
}