#2868. 「IOI2018」会议

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

题目描述

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

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

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

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

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

实现细节

你需要实现下面的函数:

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

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

输入格式

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

  • 第一行: N\ Q
  • 第二行: H_0\ H_1\ \ldots \ H_{N-1}
  • 3+j 行( 0\le j\le Q-1 ): L_j\ R_j

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

  • 1+j 行( 0\le j\le Q-1 ): C_j

样例

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

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

meeting.png

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

  • 住在山 0 上的参会者的成本是 \max \{ H_0\}=2
  • 住在山 1 上的参会者的成本是 \max \{ H_0, H_1\}=4
  • 住在山 2 上的参会者的成本是 \max \{ H_0, H_1, H_2\}=4
  • 因此,会议 0 的成本是 2+4+4=10

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

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

  • 住在山 1 上的参会者的成本是 \max \{ H_1, H_2\}=4
  • 住在山 2 上的参会者的成本是 \max \{ H_2\}=3
  • 住在山 3 上的参会者的成本是 \max \{ H_2, H_3\}=5
  • 因此,会议 1 的成本是 4+3+5=12

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


样例输入

4 2
2 4 3 5
0 2
1 3

样例输出

10
12

数据范围与提示

对于全部数据:

  • 1\le N,Q\le 7.5\times 10^5
  • 1\le H_i\le 10^9 (0\le i\le N-1)
  • 0\le L_j\le R_j\le N-1 且保证区间两两不同( 0\le j\le Q-1 )。

子任务

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