AT_arc180_d.[ARC180D] Division into 3

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

给定一个长度为 $N$ 的整数序列 $A=(A_1,A_2,\cdots,A_N)$ 。请回答以下 $Q$ 个查询。

第 $i$ $i$ 个查询：给定整数 $L_i,R_i$ $L_{i}, R_{i}$ 。对于 $B=(A_{L_i},A_{L_i+1},\cdots,A_{R_i})$ $B = (A_{L_{i}}, A_{L_{i} + 1}, \dots, A_{R_{i}})$ ，解决如下问题：
- 将 $B$ 分割为 $3$ 个非空的连续子序列。对于每个连续子序列，求出其元素的最大值。求这些最大值之和可能取得的最小值。注意，由于题目限制， $B$ 的长度至少为 $3$ ，因此一定存在至少一种分割方法。

输入以如下格式从标准输入给出。

$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

输入#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

限制条件

以第 $1$ 个查询为例。 $B=(4,3,1,1,4,5,2)$ 。将其分割为 $(4,3),(1,1),(4,5,2)$ 时，各连续子序列的最大值分别为 $4,1,5$ ，其总和为 $10$ 。不存在比 $10$ 更小的分割方式，因此该查询的答案为 $10$ 。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?