分数: 700 点
问题陈述
给你一个整数序列 A=(A_1,A_2,\cdots,A_N) 长度 N。 回答以下问题 Q 查询。
- 的 i-th 查询:您得到整数 L_i 和 R_i。
解决以下问题 B=(A_{L_i},A_{L_i+1},\cdots,A_{R_i}).
- 除法 B 分成三个非空连续子序列。对于每个连续的子序列,让我们找到其元素的最大值。找出这些最大值的最小可能总和。 在这里,问题的约束迫使 B 至少 3,因此总是至少有一种方法将其分为三个非空连续子序列。
约束
- 3 \leq N \leq 250000
- 1 \leq Q \leq 250000
- 1 \leq A_i \leq 10^8
- 1 \leq L_i \leq R_i \leq N
- R_i - L_i \geq 2
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N Q A_1 A_2 \cdots A_N L_1 R_1 L_2 R_2 \vdots L_Q R_Q
输出
打印 Q 行。的 i- 第行应包含以下问题的答案 i第一个查询。
示例输入 1
7 5 4 3 1 1 4 5 2 1 7 2 4 3 5 1 5 4 7
示例输出 1
10 5 6 9 8
让我们解释一下第一个查询。 我们有 B=(4,3,1,1,4,5,2)。 如果你把它分成 (4,3),(1,1),(4,5,2),连续子序列的最大值为 4,1,5分别,它们的总和是 10。 没有办法让这个总和变得更小,所以这个查询的答案是 10.
示例输入 2
10 15 8 3 8 10 1 5 3 1 6 4 4 6 2 5 6 9 8 10 2 9 4 10 1 5 1 8 1 3 4 8 1 10 2 10 6 10 2 6 2 6
示例输出 2
16 14 12 11 17 17 19 14 19 14 17 17 12 16 16