Description

《山海经》是以山为纲，以海为线记载古代的河流、植物、动物及矿产等情况，而且每一条记录路线都不会有重复的山出现。某天，你的地里老师想重游《山海经》中的路线，为了简化问题，老师已经把每座山用一个整数表示他对该山的喜恶程度，他想知道第a座山到第b座山的中间某段路(I,j),使得他感到是最满意的，即(I,j)这条路上所有山的喜恶程度之和是所有(c,d)(a<=c<=d<=b)最大。于是老师便向你请教，你能帮助他吗？值得注意的是，在《山海经》中，第i座山只能到达第i+1座山。

Input

输入第一行是两个数n,m,2<=n<=100000,1<=m<=100000,n表示一共有n座山，m表示老师想查询的数目。
　　第二行是n个整数，代表n座山的喜恶度，绝对值均小于10000。
　　以下m行每行有两个数，a,b,1<=a<=b<=n,表示第a座山到第b座山。

Output

一共有m行，每行有三个数I,j,s,表示从第i座山到第j座山总的喜恶度为s。显然，对于每个查询，有a<=i<=j<=b,如果有多组解，则输出i最少的，如果i也相等，则输出j最少的解。

Sample Input

1
2
3
4
5
5 3
5 -6 3 -1 4
1 3
1 5
5 5

Sample Output

1
2
3
1 1 5
3 5 6
5 5 4

Solution

简化一下题目，给定你一个区间[l,r][l,r]，请你求出区间最大子段和

这道题可以用线段树来做。

难点主要在于维护（即pushup）

对于一个子段和，我们分情况来进行讨论

讨论之前，先定义几个东西（封装成一个结构体不然会很乱！）

sumcsumc表示区间最大子段和，clcl表示子段和左端点，crcr表示子段和右端点

sumlsuml表示区间最大前缀和，frfr表示前缀和右端点，（显然左端点为区间左端点）

sumrsumr表示区间最大后缀和，flfl表示前缀和左端点，（显然右端点为区间右端点）

sumsum表示区间和

再定义lsls为左儿子，rsrs为右儿子

开始分类讨论（讨论过程中同步更新端点（clcl，crcr，frfr，flfl）按照题目要求的优先值）。

（可以自己画图，感性理解一下）

对于sumlsuml，它有2种情况

  • ls.sumlls.suml
  • ls.sum+rs.sumlls.sum+rs.suml

对于sumrsumr，它有2种情况

  • rs.sumrrs.sumr
  • ls.sumr+rs.sumls.sumr + rs.sum

对于sumcsumc，它有3种情况

  • ls.sumcls.sumc
  • rs.sumcrs.sumc
  • ls.sumr+rs.sumlls.sumr+rs.suml

在pushup中小心地讨论即可

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
// #pragma GCC optimize(3,"Ofast","inline")
#include <cstdio>
#define N 100005
#define LL long long
#define inf (-1000000005)
using namespace std;
LL n, m;
struct Data {
	LL gl, gr, gc, sum, fr, fl, cl, cr;
} c[N << 2];
inline LL read() {
	LL t = 0; bool f = 0; char v = getchar();
	for (; v < 48 || v > 57; v = getchar()) f |= (v == 45);
	for (; v > 47 && v < 58; v = getchar())
		t = (t << 3) + (t << 1) + (v ^ 48);
	return f ? (~t + 1) : t;
}
void pushup(Data &w, Data l, Data r) {
	LL t1 = l.gl, t2 = l.sum + r.gl;
	if (t1 >= t2) w.gl = t1, w.fr = l.fr;
	else w.gl = t2, w.fr = r.fr;
	LL t3 = r.gr, t4 = r.sum + l.gr;
	if (t3 > t4) w.gr = t3, w.fl = r.fl;
	else w.gr = t4, w.fl = l.fl;
	LL t5 = l.gc, t6 = r.gc;
	if (t5 >= t6) w.gc = t5, w.cl = l.cl, w.cr = l.cr;
	else w.gc = t6, w.cl = r.cl, w.cr = r.cr;
	LL t7 = l.gr + r.gl;
	if (t7 > w.gc) w.gc = t7, w.cl = l.fl, w.cr = r.fr;
	else if (t7 == w.gc) {
		if (w.cl > l.fl) w.cl = l.fl, w.cr = r.fr;
		else if (w.cl == l.fl && w.cr > r.fr) w.cr = r.fr;
	}w.sum = l.sum + r.sum;
}
void build(LL w, LL l, LL r) {
	if (l >= r) {
		LL x = read();
		c[w] = Data{x, x, x, x, l, l, l, l};
		return ;
	}LL mid = (l + r) >> 1;
	build(w << 1, l, mid), build(w << 1 | 1, mid + 1, r);
	pushup(c[w], c[w << 1], c[w << 1 | 1]);
}
Data query(LL w, LL l, LL r, LL L, LL R) {
	if (L <= l && r <= R) return c[w];
	LL mid = (l + r) >> 1;
	Data t1 = Data{inf, inf, inf, inf, 0, 0, 0, 0};
	Data t2 = Data{inf, inf, inf, inf, 0, 0, 0, 0}, t;
	if (L <= mid) t1 = query(w << 1, l, mid, L, R);
	if (R > mid) t2 = query(w << 1 | 1, mid + 1, r, L, R);
	return pushup(t, t1, t2), t;
}
int main()
{
	n = read(), m = read();
	build(1, 1, n);
	for (LL a, b; m--;) {
		scanf("%lld%lld", &a, &b);
		Data t = query(1, 1, n, a, b);
		printf("%lld %lld %lld\n", t.cl, t.cr, t.gc);
	}
}