Skip to content

14134: 【原4134】开天辟地

题目

题目描述

author: Lmxyy 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4134

Description

dhh又称为h神,是一位仙界巨佬,拥有这无尽的仙力。

每当下雨时,山间就会积起大大小小的水洼。

下面是山的示意图:

.....X
..X..X
..XX.X
X.XX.X
X.XX.X
XXXXXX

‘X’代表土地,‘.’代表空气。

山是二维的,长\(N\)个单位,第\(i\)个单位的地方高度为\(h_i\)。上面描述的山就是\(N = 6\),\(h = { 3,1,5,4,1,6 }\)的情况。

现在dhh不知怎么的,想要开天辟地。他看某些山不顺眼,就准备将他们磨平,只保留\(A_i\)到\(B_i\)这一段山脉,那么在dhh磨平后这些山最多能够积起多少单位的水呢?

例如,\(A_i = 2\),\(B_i = 6\)时,积水情况如下:

....X
.X**X
.XX*X
.XX*X
.XX*X
XXXXX

‘*’代表积水。

由于dhh还拥有时间宝石,他可以在将山夷为平地后让时间倒退,再重新选择保留那段山。夷平一共\(Q\)次。由于使用时间宝石会耗费dhh的仙力,所以每次他夷平山脉后,请你告诉他可以积多少水,这样好让他最后决定保留哪座山脉。

Input Format

第一行两个正整数\(N\)和\(Q\)。

接下来一行\(N\)个数\(h_i\)。

最后\(Q\)行,每行两个数\(A_i,B_i\)。

Output Format

对于每组询问,输出一行答案。

Sample Input 1

11 11
2 4 5 3 2 6 1 3 1 8 1 
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11

Sample Output 1

0
0
0
0
0
5
5
7
7
18
18

Sample Input 2

5 3
10 1 1 1 10
1 5
1 2
4 5

Sample Output 2

27
0
0

Data Range

对于\(30\%\)的数据,\(N\)和\(Q\)不超过\(20\)。

对于\(100\%\)的数据,\(1 \le N,Q \le 3 \times 10^5\),\(1 \le h_i \le 10^9\),\(1 \le A_i \le B_i \le N\)。

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!