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

#include <cmath>
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
template<class T>inline void Read(T& x) {
	x = 0; bool flag = 0; char ch = getchar();
	while(ch<'0'||ch>'9') { if(ch == '-') flag = 1; ch = getchar(); }
	while('0'<=ch&&ch<='9') { x=x*10+ch-'0'; ch = getchar(); }
	if(flag) x=-x;
}
#define maxn 200010
int a[maxn];
struct tree {
	int L,R,M,S;
	int lc,rc,ml,mr;
	tree() { L = R = M = S = lc = rc = ml = mr = 0 ;}
}T[maxn << 2];
#define left (o << 1)
#define right (o << 1 | 1)
inline tree update(tree x,tree y) {
	tree res;
	res.L = x.L;   res.lc = x.lc; 
	res.R = y.R;   res.rc = y.rc;   
	res.ml = x.ml; res.mr = x.mr; res.M = x.M;
	res.S = x.S + y.S;
	if(x.S+y.L > res.L) res.L = x.S+y.L,res.lc = y.lc;
	if(x.R+y.S >=res.R) res.R = x.R+y.S,res.rc = x.rc;
	if(x.R+y.L > res.M) res.M = x.R+y.L,res.ml = x.rc,res.mr = y.lc;  
	if(y.M > res.M) res.M = y.M,res.ml = y.ml,res.mr = y.mr;
	return res;
}
inline void build(int o,int l,int r) {
	if(l == r) {
		T[o].S = T[o].L = T[o].R = T[o].M = a[l];
		T[o].lc = T[o].rc = T[o].ml = T[o].mr = l;
		return ;
	}
	int mid = (l + r) >> 1;
	build(left,l,mid);
	build(right,mid+1,r);
	T[o] = update(T[left],T[right]);
}
int Qx = 0,Qy = 0;
inline tree query(int o,int l,int r) {
	if(Qx <= l && r <= Qy) return T[o];
	int mid = (l + r) >> 1;
	if(Qy <= mid) return query(left, l , mid);
	else if(Qx >  mid) return query(right,mid+1,r);
	else {
		tree x,y;
		x = query(left, l , mid);
		y = query(right,mid+1,r);
		return update(x,y);
	}
}
int main() {
	freopen("hill.in","r",stdin);
	freopen("hill.out","w",stdout);
	int n = 0,m = 0;
	Read(n); Read(m);
	for(int i = 1;i <= n;++ i) Read(a[i]);
	build(1,1,n);
	tree tmp; 
	while(m --) {
		Read(Qx); Read(Qy);
		tmp = query(1,1,n);
		printf("%d %d %d\n",tmp.ml,tmp.mr,tmp.M);
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}