[IOI2018] meetings 会议

本题为交互题，但在此请提交**完整程序**。 本题因为测试点过多，文件过大，只选择了33个测试点进行测评（涵盖了所有子任务）。剩余11组数据可下载数据自行测评。 https://ioi2018.jp/wp-content/tasks/contest2/meetings.zip

有 $N$ 座山横着排成一行，从左到右编号为从 $0$ 到 $N-1$。山的高度为 $H_i$（$0\leq i\leq N-1$）。每座山的顶上恰好住着一个人。 你打算举行 $Q$ 个会议，编号为从 $0$ 到 $Q-1$。会议 $j$（$0\leq j\leq Q-1$） 的参加者为住在从山 $L_j$ 到山 $R_j$（包括 $L_j$ 和 $R_j$）上的人（$0\leq L_j\leq R_j\leq N-1$）。对于该会议，你必须选择某个山 $x$ 做为会议举办地（$L_j\leq x\leq R_j$）。举办该会议的成本与你的选择有关，其计算方式如下： - 来自每座山 $y$（$L_j\leq y\leq R_j$） 的参会者的成本，等于在山 $x$ 和 $y$ 之间（包含 $x$ 和 $y$）的所有山的最大高度。特别地，来自山 $x$ 的参会者的成本是 $H_x$，也就是山 $x$ 的高度。 - 会议的成本等于其所有参会者的成本之和。 你想要用最低的成本来举办每个会议。 注意，所有的参会者将在每次会议后回到他们自己的山；所以一个会议的成本不会受到先前会议的影响。

输入的第一行包含两个正整数 $N$ 和 $Q$，其意义见题目描述。 第二行包含 $N$ 个正整数 $H_0,H_1,\cdots, H_{N-1}$，表示这些山的高度。 第 $3+j$ 行（$0\leq j\leq Q-1$），每行两个整数 $L_j, R_j$，表示这些会议的参会者的范围。

共 $Q$ 行，第 $1+j$ 行（$0\leq j\leq Q-1$）一个整数 $C_j$，表示举办会议 $j $ 的最低的可能成本。

4 2
2 4 3 5
0 2
1 3

10
12

3 3
2 1 2
0 0
0 1
0 2

2
3
5

5 1
1000000000 1000000000 1 1000000000 1000000000
0 4

4000000001

15 10
10 71 84 33 6 47 23 25 52 64 70 31 22 31 2
5 10
3 7
0 13
8 12
0 0
1 3
7 13
1 13
10 12
1 1

281
180
828
263
10
201
364
744
123
71

### 样例#1解释 会议$j=0$有$L_j=0$和$R_j=2$，所以将由住在山$0$、$1$和$2$上的人参加。如果山$0$被选做举办地，会议$0$的成本计算如下： - 住在山$0$上的参会者的成本是$\max\lbrace H_0\rbrace=2$。 - 住在山$1$上的参会者的成本是$\max\lbrace H_0,H_1\rbrace=4$。 - 住在山$2$上的参会者的成本是$\max\lbrace H_0,H_1,H_2\rbrace=4$。 - 因此，会议$0$的成本是$2+4+4=10$。 不可能以更低的成本来举办会议$0$了，因此会议$0$的最低成本是$10$。 会议$j=1$有$L_j=1$和$R_j=3$，因此将由住在山$1$、$2$和$3$上的人参加。如果山$2$被选做举办地，会议$1$的成本计算如下： - 住在山$1$上的参会者的成本是$\max\lbrace H_1,H_2\rbrace=4$。 - 住在山$2$上的参会者的成本是$\max\lbrace H_2\rbrace=3$。 - 住在山$3$上的参会者的成本是$\max\lbrace H_1,H_2,H_3\rbrace=5$。 - 因此，会议$1$的成本是$4+3+5=12$。 不可能以更低的成本来举办会议$1$了，所以会议$1$的最低成本是$12$。 ### 限制条件 - $1\leq N\leq 750\space000$ - $1\leq Q\leq 750\space000$ - $1\leq H_i\leq1\space000\space000\space000$ - $0\leq L_j\leq R_j\leq R-1(0\leq j\leq Q-1)$ - $(L_j,R_j)\neq(L_k,R_k)(0\leq j<k\leq Q-1)$ ### 子任务 1. (4分) $N\leq3000,Q\leq10$ 2. (15分) $N\leq5000,Q\leq5000$ 3. (17分) $N\leq100\space000,Q\leq100\space000,H_i\leq2(0\leq i\leq N-1)$ 4. (24分) $N\leq100\space000,Q\leq100\space000,H_i\leq20(0\leq i\leq N-1)$ 5. (40分) 没有附加限制 ### Author Riku Kawasaki (Japan) ### Source IOI 2018 D2T3