#2868. 「IOI2018」会议

内存限制:805 MiB 时间限制:4500 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: HeRaNO

题目描述

NN 座山横着排成一行,从左到右编号为从 00N1N-1。山 ii 的高度为 HiH_i0iN10\le i\le N-1)。每座山的顶上恰好住着一个人。

你打算举行 QQ 个会议,编号为从 00Q1Q-1。会议 jj0jQ10\le j\le Q-1)的参加者为住在从山 LjL_j 到山 RjR_j(包括 LjL_jRjR_j)上的人(0LjRjN10\le L_j\le R_j\le N-1)。对于该会议,你必须选择某个山 xx 做为会议举办地(LjxRjL_j\le x\le R_j)。举办该会议的成本与你的选择有关,其计算方式如下:

  • 来自每座山 yyLjyRjL_j\le y\le R_j)的参会者的成本,等于在山 xxyy 之间(包含 xxyy)的所有山的最大高度。特别地,来自山 xx 的参会者的成本是 HxH_x,也就是山 xx 的高度。
  • 会议的成本等于其所有参会者的成本之和。

你想要用最低的成本来举办每个会议。

注意,所有的参会者将在每次会议后回到他们自己的山;所以一个会议的成本不会受到先前会议的影响。

实现细节

你需要实现下面的函数:

int64[] minimum_costs(int[] H, int[] L, int[] R)
  • H:长度为 NN 的数组,表示这些山的高度。
  • LR:两个长度为 QQ 的数组,表示这些会议的参会者的范围。
  • 该函数应返回一个长度为 QQ 的数组 CCCjC_j0jQ10\le j\le Q-1)必须是举办会议 jj 的最低的可能成本。
  • 注意,NNQQ 的值是数组的长度,题目中所有数组均用 vector 实现。

由于本题的特殊性,改为传统题方式测评。

输入格式

评测程序示例读取如下格式的输入数据(即为输入格式):

  • 第一行:N QN\ Q
  • 第二行:H0 H1  HN1H_0\ H_1\ \ldots \ H_{N-1}
  • 3+j3+j 行(0jQ10\le j\le Q-1):Lj RjL_j\ R_j

评测程序示例将以如下格式输出 minimum_costs 的返回值(即为输出格式):

  • 1+j1+j 行(0jQ10\le j\le Q-1):CjC_j

样例

N=4,H=[2,4,3,5],Q=2,L=[0,1]N=4,H=[2,4,3,5],Q=2,L=[0,1]R=[2,3]R=[2,3]

评测程序调用 minimum_costs([2, 4, 3, 5], [0, 1], [2, 3])

meeting.png

会议 j=0j=0Lj=0L_j=0Rj=2R_j=2,所以将由住在山 0,10,122 上的人参加。如果山 00 被选做举办地,会议 00 的成本计算如下:

  • 住在山 00 上的参会者的成本是 max{H0}=2\max \{ H_0\}=2
  • 住在山 11 上的参会者的成本是 max{H0,H1}=4\max \{ H_0, H_1\}=4
  • 住在山 22 上的参会者的成本是 max{H0,H1,H2}=4\max \{ H_0, H_1, H_2\}=4
  • 因此,会议 00 的成本是 2+4+4=102+4+4=10

不可能以更低的成本来举办会议 00 了,因此会议 00 的最低成本是 1010

会议 j=1j=1Lj=1L_j=1Rj=3R_j=3,所以将由住在山 1,21,233 上的人参加。如果山 22 被选做举办地,会议 11 的成本计算如下:

  • 住在山 11 上的参会者的成本是 max{H1,H2}=4\max \{ H_1, H_2\}=4
  • 住在山 22 上的参会者的成本是 max{H2}=3\max \{ H_2\}=3
  • 住在山 33 上的参会者的成本是 max{H2,H3}=5\max \{ H_2, H_3\}=5
  • 因此,会议 11 的成本是 4+3+5=124+3+5=12

不可能以更低的成本来举办会议 11 了,因此会议 11 的最低成本是 1212


样例输入

4 2
2 4 3 5
0 2
1 3

样例输出

10
12

数据范围与提示

对于全部数据:

  • 1N,Q7.5×1051\le N,Q\le 7.5\times 10^5
  • 1Hi1091\le H_i\le 10^9 (0iN1)(0\le i\le N-1)
  • 0LjRjN10\le L_j\le R_j\le N-1 且保证区间两两不同(0jQ10\le j\le Q-1)。

子任务

  1. (4 分)N3000,Q10N\le 3000,Q\le 10
  2. (15 分)N5000,Q5000N\le 5000,Q\le 5000
  3. (17 分)N,Q105,Hi2 (0iN1)N,Q\le 10^5,H_i\le 2\ (0\le i\le N-1)
  4. (24 分)N,Q105,Hi20 (0iN1)N,Q\le 10^5,H_i\le 20\ (0\le i\le N-1)
  5. (40 分)没有附加限制