记录编号	340892	评测结果	AAAAAAAA
题目名称	山海经	最终得分	100
用户昵称	_Itachi	是否通过	通过
代码语言	C++	运行时间	2.762 s
提交时间	2016-11-07 07:43:51	内存使用	12.88 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=100005;
struct Rabit_q{int lmax,l,rmax,r,ma,s,t,sum;}f[maxn<<2];
int n,m,a[maxn],s,t;
struct Rabit_carrot{
	void Rabit_up(int RT){
		Rabit_q ls=f[RT<<1],rs=f[RT<<1|1],&rt=f[RT];
		rt.sum=ls.sum+rs.sum;
		if(ls.sum+rs.lmax>ls.lmax)
			rt.lmax=ls.sum+rs.lmax,rt.l=rs.l;
		else rt.lmax=ls.lmax,rt.l=ls.l;
		if(rs.sum+ls.rmax>rs.rmax)
			rt.rmax=rs.sum+ls.rmax,rt.r=ls.r;
		else rt.rmax=rs.rmax,rt.r=rs.r;
		if(ls.ma>=rs.ma&&ls.ma>=ls.rmax+rs.lmax)
			rt.ma=ls.ma,rt.s=ls.s,rt.t=ls.t;
		else if(ls.rmax+rs.lmax>ls.ma&&ls.rmax+rs.lmax>=rs.ma)
			rt.ma=ls.rmax+rs.lmax,rt.s=ls.r,rt.t=rs.l;
		else rt.ma=rs.ma,rt.s=rs.s,rt.t=rs.t;
	}
	void Rabit_set(int rt,int l,int r){
		if(l==r){
			f[rt].lmax=f[rt].rmax=f[rt].ma=f[rt].sum=a[l],
			f[rt].l=f[rt].r=f[rt].s=f[rt].t=l;
			return;	
		}	
		int mid=(l+r)>>1;
		Rabit_set(rt<<1,l,mid),Rabit_set(rt<<1|1,mid+1,r);
		Rabit_up(rt);
	}
	Rabit_q Rabit_get(int RT,int l,int r,int mid){
		Rabit_q ls=Rabit_get(RT<<1,l,mid),rs=Rabit_get(RT<<1|1,mid+1,r),rt;
		rt.sum=ls.sum+rs.sum;
		if(ls.sum+rs.lmax>ls.lmax)
			rt.lmax=ls.sum+rs.lmax,rt.l=rs.l;
		else rt.lmax=ls.lmax,rt.l=ls.l;
		if(rs.sum+ls.rmax>rs.rmax)
			rt.rmax=rs.sum+ls.rmax,rt.r=ls.r;
		else rt.rmax=rs.rmax,rt.r=rs.r;
		if(ls.ma>=rs.ma&&ls.ma>=ls.rmax+rs.lmax)
			rt.ma=ls.ma,rt.s=ls.s,rt.t=ls.t;
		else if(ls.rmax+rs.lmax>ls.ma&&ls.rmax+rs.lmax>=rs.ma)
			rt.ma=ls.rmax+rs.lmax,rt.s=ls.r,rt.t=rs.l;
		else rt.ma=rs.ma,rt.s=rs.s,rt.t=rs.t;
		return rt;
	}
	Rabit_q Rabit_get(int rt,int l,int r){
		if(s<=l&&r<=t)return f[rt];
		int mid=(l+r)>>1;
		if(t<=mid)return Rabit_get(rt<<1,l,mid);
		if(s>mid)return Rabit_get(rt<<1|1,mid+1,r);
		return Rabit_get(rt,l,r,mid);
	}
}_;
void Rabit_in(){
	scanf("%d%d",&n,&m);int i;
	for(i=1;i<=n;i++)scanf("%d",&a[i]);
	_.Rabit_set(1,1,n);	
}
void Rabit_main(){
	Rabit_in();Rabit_q res;
	while(m--){
		scanf("%d%d",&s,&t);
		res=_.Rabit_get(1,1,n);
		printf("%d %d %d\n",res.s,res.t,res.ma);
	}
}
int main(){
#define _Rabit _RABIT
#ifdef _Rabit
	freopen("hill.in","r",stdin);
	freopen("hill.out","w",stdout);
#endif
	Rabit_main();
#ifndef _Rabit
	getchar(),getchar();
#endif
	fclose(stdin);fclose(stdout);
	return 0;
}