记录编号	380519	评测结果	AAAAAAAA
题目名称	山海经	最终得分	100
用户昵称	Ostmbh	是否通过	通过
代码语言	C++	运行时间	1.468 s
提交时间	2017-03-09 16:46:16	内存使用	57.51 MiB

#include<cstdio>
#include<algorithm>
#define maxn 1000000
#define INF 1<<25
#define u tree[x]
#define lc tree[x<<1]
#define rc tree[x<<1|1]
using namespace std;
struct node{
	int l,r,val;
};
node operator + (node x, node y) {
		return (node){min(x.l,y.l),max(x.r,y.r),x.val+y.val};
	}
class poi{
public:
	int l,r;
	node lv,rv,max,sum;
	poi(){
		lv=(node){1,1,-INF};
		rv=(node){1,1,-INF};
		max=(node){1,1,-INF};
		sum=(node){1,1,-INF};
	}
}tree[maxn];
int a[maxn];
node max (node a,node b){
	if (a.val!=b.val) return a.val<b.val?b:a;
	else
	if (a.l!=b.l) return a.l<b.l?a:b; 
	else
	return a.r<b.r?a:b;
}
void update(int x){
	u.sum=lc.sum+rc.sum;
	u.lv=max(rc.lv+lc.sum,lc.lv);
	u.rv=max(lc.rv+rc.sum,rc.rv);
	u.max=max(u.max,lc.max);
	u.max=max(u.max,rc.max);
	u.max=max(u.max,lc.rv+rc.lv);
}
void maketree(int x,int l,int r){
	u.l=l;u.r=r;
	if (l==r){
		u.sum=(node){l,r,a[l]};
		u.max=(node){l,r,a[l]};
		u.lv=(node){l,r,a[l]};
		u.rv=(node){l,r,a[l]};
	}
	else{
		maketree(x<<1,l,(l+r>>1));
		maketree(x<<1|1,(l+r>>1)+1,r);
		update(x);
	}
}
poi max(int x,int l,int r){
	if (l<=u.l&&u.r<=r){
		return u;
	}
	else{
		poi a,b,tmp;
		if (l<=lc.r){
			a=max(x<<1,l,r);
		}
		if (r>=rc.l){
			b=max(x<<1|1,l,r);
		}
		tmp.max=max(a.max,b.max);
		tmp.max=max(a.rv+b.lv,tmp.max);
		tmp.lv=max(a.lv,a.sum+b.lv);
		tmp.rv=max(b.rv,b.sum+a.rv);
		tmp.sum=a.sum+b.sum;
		return tmp;
	}
}
int main(){
	freopen("hill.in","r",stdin);
	freopen("hill.out","w",stdout);
	int n,m;
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	maketree(1,1,n);
	int l,r;
	for(int i=1;i<=m;i++){
		scanf("%d %d",&l,&r);
		poi ans=max(1,l,r);
		printf("%d %d %d\n",ans.max.l,ans.max.r,ans.max.val);
	}
	return 0;
}