山海经

题目背景

“南山之首日鹊山。其首日招摇之山，临于西海之上，多桂，多金玉。有草焉，其状如韭而青华，其名日祝余，食之不饥……又东三百里，日堂庭之山，多棪木，多白猿，多水玉，多黄金。

又东三百八十里，日猨翼之山，其中多怪兽，水多怪鱼，多白玉，多蝮虫，多怪蛇，名怪木，不可以上。……”

题目描述

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

输入格式

输入第1行是两个数 $n$ ， $m$ ， $2≤n≤100000$ ， $1≤m≤100000$ ， $n$ 表示一共有 $n$ 座山， $m$ 表示老师想查询的数目。

第2行是 $n$ 个整数，代表 $n$ 座山的喜恶度，绝对值均小于 $10000$ 。

以下 $m$ 行每行有 $a$ ， $b$ 两个数， $1≤a≤j≤b≤m$ ，表示第 $a$ 座山到第 $b$ 座山。

输出格式

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

样例 #1

样例输入 #1

15 120
9 -10 4 -2 4 -5 4 -3 6 -11 8 -3 4 -5 3
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
2 2
2 3
2 4
2 5
2 6
2 7
2 8
2 9
2 10
2 11
2 12
2 13
2 14
2 15
3 3
3 4
3 5
3 6
3 7
3 8
3 9
3 10
3 11
3 12
3 13
3 14
3 15
4 4
4 5
4 6
4 7
4 8
4 9
4 10
4 11
4 12
4 13
4 14
4 15
5 5
5 6
5 7
5 8
5 9
5 10
5 11
5 12
5 13
5 14
5 15
6 6
6 7
6 8
6 9
6 10
6 11
6 12
6 13
6 14
6 15
7 7
7 8
7 9
7 10
7 11
7 12
7 13
7 14
7 15
8 8
8 9
8 10
8 11
8 12
8 13
8 14
8 15
9 9
9 10
9 11
9 12
9 13
9 14
9 15
10 10
10 11
10 12
10 13
10 14
10 15
11 11
11 12
11 13
11 14
11 15
12 12
12 13
12 14
12 15
13 13
13 14
13 15
14 14
14 15
15 15

样例输出 #1

2023/4/30 18:09