P14668 [ICPC 2025 Seoul R] Badge Relay

一个研究设施运营着两栋建筑：左实验室和右实验室，它们由一条安全走廊连接。开始时，所有被选中的员工都站在左实验室。 - 走廊一次最多容纳两人。 - 恰好有一个安全门禁卡，每次穿越走廊（无论是一人还是两人同行）都必须携带此卡。 - 如果两人同行，他们必须并排行走，且穿越时间等于较慢者的时间。 - 如果在一次从左实验室到右实验室的穿越后，左实验室仍有员工剩余，那么在开始下一次从左到右的穿越之前，右实验室中的某人必须将门禁卡带回左实验室。 为了观察策略如何影响总时间，考虑四名员工，其各自的穿越时间为 $\{1, 2, 5, 10\}$。一种可能的策略如下：如果 $(1, 2)$ 先穿越（耗时 $2$ 分钟），然后 $(1)$ 带着卡返回（$1$ 分钟），接着 $(1, 5)$ 穿越（$5$ 分钟），$(1)$ 返回（$1$ 分钟），最后 $(1, 10)$ 穿越（$10$ 分钟），总时间为 $19$ 分钟。然而，存在另一种（更好的）策略：如果 $(1, 2)$ 先穿越（$2$ 分钟），$(1)$ 返回（$1$ 分钟），然后 $(5, 10)$ 一起穿越（$10$ 分钟），$(2)$ 返回（$2$ 分钟），最后 $(1, 2)$ 再次穿越（$2$ 分钟），总时间变为 $17$ 分钟，这比第一种策略的总穿越时间更小。为方便起见，两种穿越序列总结于下表 1 和表 2。 :::align{center} **表 1. 序列 A（总计 19 分钟）** ::: | 步骤 | 操作 | 左实验室（之后） | 右实验室（之后） | 耗时（分钟） | 累计（分钟） | |:-:|:-:|:-:|:-:|:-:|:-:| | 0 | - | $\{1, 2, 5, 10\}$ | $\emptyset$ | - | - | | 1 | 穿越 $(1, 2)$ | $\{5, 10\}$ | $\{1, 2\}$ | $2$ | $2$ | | 2 | 返回 $(1)$ | $\{1, 5, 10\}$ | $\{2\}$ | $1$ | $3$ | | 3 | 穿越 $(1, 5)$ | $\{10\}$ | $\{1, 2, 5\}$ | $5$ | $8$ | | 4 | 返回 $(1)$ | $\{1, 10\}$ | $\{2, 5\}$ | $1$ | $9$ | | 5 | 穿越 $(1, 10)$ | $\emptyset$ | $\{1, 2, 5, 10\}$ | $10$ | $19$ | :::align{center} **表 2. 序列 B（总计 17 分钟）** ::: | 步骤 | 操作 | 左实验室（之后） | 右实验室（之后） | 耗时（分钟） | 累计（分钟） | |:-:|:-:|:-:|:-:|:-:|:-:| | 0 | - | $\{1, 2, 5, 10\}$ | $\emptyset$ | - | - | | 1 | 穿越 $(1, 2)$ | $\{5, 10\}$ | $\{1, 2\}$ | $2$ | $2$ | | 2 | 返回 $(1)$ | $\{1, 5, 10\}$ | $\{2\}$ | $1$ | $3$ | | 3 | 穿越 $(5, 10)$ | $\{1\}$ | $\{2, 5, 10\}$ | $10$ | $13$ | | 4 | 返回 $(2)$ | $\{1, 2\}$ | $\{5, 10\}$ | $2$ | $15$ | | 5 | 穿越 $(1, 2)$ | $\emptyset$ | $\{1, 2, 5, 10\}$ | $2$ | $17$ | 现在给你 $n$ 名员工。员工 $i$ 需要 $T_i$ 分钟来穿越走廊。同时给出 $q$ 次询问。每次询问由以下参数定义： - 一个下标范围 $[x, y]$（包含端点）， - 一个时间范围 $[a, b]$（包含端点），以及 - 一个选择上限 $K$（你最多可以选择多少名员工）。 对于每次询问，考虑所有下标位于 $[x, y]$ 内且穿越时间位于 $[a, b]$ 内的员工。在这些员工中，选择 $K$ 名穿越时间最小的员工。如果这样的员工少于 $K$ 名，则选择所有符合条件的员工。这些被选中的员工都从拥有唯一门禁卡的左实验室出发。根据上述规则，你需要计算**所有被选中员工**到达右实验室所需的**最小总穿越时间**。如果没有员工被选中，答案应为 $0$。 给定 $n$ 名员工，其穿越时间为 $T_1, \cdots, T_n$，以及 $q$ 次形式为 $(x, y, a, b, K)$ 的询问，请编写一个程序处理这些询问，并为每次询问输出被选中员工从左实验室移动到右实验室的最小总穿越时间。

你的程序需要从标准输入读取数据。输入的第一行包含两个整数 $n$ 和 $q$ ($1 \le n, q \le 100,000$)，其中 $n$ 是员工数量，$q$ 是询问次数。员工编号从 $1$ 到 $n$。第二行包含 $n$ 个整数 $T_1, \cdots, T_n$ ($1 \le T_i \le 10^9$)，其中 $T_i$ 是员工 $i$ ($1 \le i \le n$) 的穿越时间。接下来的 $q$ 行每行包含五个整数 $x, y, a, b, K$，其含义如上所述，其中 $1 \le x \le y \le n$； $1 \le a \le b \le 10^9$； $1 \le K \le n$。

你的程序需要向标准输出写入数据。对于每次询问，输出一行，包含被选中员工从左实验室移动到右实验室的最小总穿越时间。如果没有员工被选中，输出 $0$。

翻译由 DeepSeek V3 完成