记录编号	305688	评测结果	AAAAAAAA
题目名称	山海经	最终得分	100
用户昵称	KZNS	是否通过	通过
代码语言	C++	运行时间	1.715 s
提交时间	2016-09-10 22:29:47	内存使用	21.65 MiB

//KZNS
//Best Wil
#include <cstdio>
#define Nmax 100003
class qj {
public:
	int s, l, r;
	inline void fr(const int ss, const int ll, const int rr) {
		s = ss;
		l = ll;
		r = rr;
	}
};
inline qj max(const qj a, const qj b) {
	if (a.s == b.s) {
		if (a.l == b.l) {
			if (a.r < b.r)
				return a;
			else
				return b;
		}
		else {
			if (a.l < b.l)
				return a;
			else
				return b;
		}
	}
	else {
		if (a.s < b.s)
			return b;
		else
			return a;
	}
}
qj operator + (const qj a, const qj b) {
	qj u;
	u.s = a.s + b.s;
	u.l = a.l;
	u.r = b.r;
	return u;
}
class poi {
public:
	int l, r;
	qj lp, rp, dp, sp;
} tr[Nmax<<2];
poi operator + (poi a, poi b) {
	poi ans;
	ans.l = a.l;
	ans.r = b.r;
	ans.sp = a.sp + b.sp;
	ans.lp = max(a.lp, a.sp + b.lp);
	ans.rp = max(a.rp + b.sp, b.rp);
	ans.dp = max(a.rp + b.lp, max(a.dp, b.dp));
	return ans;
}
#define fc tr[x]
#define lc tr[x<<1]
#define rc tr[x<<1^1]
void make_tree(int x, int l, int r) {
	fc.l = l;
	fc.r = r;
	if (l == r) {
		int s;
		scanf("%d", &s);
		fc.sp.fr(s, l, r);
		fc.lp = fc.rp = fc.dp = fc.sp;
	}
	else {
		make_tree(x<<1, l, l+r>>1);
		make_tree(x<<1^1, (l+r>>1)+1, r);
		fc = lc + rc;
	}
}
poi Qin(int x, int l, int r) {
	if (l <= fc.l && fc.r <= r)
		return fc;
	else {
		poi u1, u2;
		u1.l = 0;
		u2.l = 0;
		if (l <= lc.r)
			u1 = Qin(x<<1, l, r);
		if (rc.l <= r)
			u2 = Qin(x<<1^1, l, r);
		if (u1.l == 0)
			return u2;
		if (u2.l == 0)
			return u1;
		return u1+u2;
	}
}
int main() {
	freopen("hill.in", "r", stdin);
	freopen("hill.out", "w", stdout);
	int N, Q;
	scanf("%d %d", &N, &Q);
	make_tree(1, 1, N);
	int a, b;
	poi u;
	qj ans;
	while (Q--) {
		scanf("%d %d", &a, &b);
		u = Qin(1, a, b);
		ans = max(u.dp, max(u.lp, u.rp));
		printf("%d %d %d\n", ans.l, ans.r, ans.s);
	}
	return 0;
}
//All Illu
//UBWH