题目大意 一共有 nnn 个关卡，每个关卡分为解密和战斗两部分，挑战关卡有两个限制： * 对于不同关卡，只有完成了前一关的解密部分才能进行下一关的解密部分； * 对于同一关卡，只有完成了这一关卡的解密部分才能进行这一关的战斗部分。 第 iii 关的解密部分需要耗时 aia_iai ，战斗部分需要耗时 bib_ibi ，完成了一关的揭秘和战斗部分才视为完成这一关。对于 qqq 个询问，求完成 kkk 个关卡的最短用时。 解题思路 首先考虑完成 kkk 个关卡，我们需要至少完成前 kkk 个解密部分 ，完成 bib_ibi 之前我们需要至少完成前 iii 个解密部分。 接下来我们需要考虑的是选择完成哪几个关卡所花的时间最少。由于询问次数只有 100100100 ，所以对于每一个询问可以尝试使用 O(n)O(n)O(n) 甚至 O(nlogn)O(nlogn)O(nlogn) 的复杂度去完成。由于完成解密部分一定是连续的，所以我们可以先用前缀和 sis_isi 求出前 iii 个解密部分所花时间是多少。 我们可以枚举最后一个被完成的关卡的哪个，此时的时间花费是 si+bis_i+b_isi +bi ，其余的 k−1k-1k−1 个战斗部分选择 bib_ibi 最小的 k−1k-1k−1 个，但是这样的做法时间复杂度会来到 O(n2)O(n^2)O(n2) ，显然是不合理的。其实我们可以通过优先队列优化选 bib_ibi 的过程，我们先选出前 kkk 关卡完成，将 bib_ibi 都存入优先队列中，往后枚举时，设当前枚举的位置为 jjj ，如果 bjb_jbj 小于优先队列中最大的元素，则可以把 bjb_jbj 与优先队列中最大元素替换。每次算出所需要的时间，更新答案。这样查询的时间复杂度为 O(nlogn)O(nlogn)O(nlogn) 。 总时间复杂度为 O(n+knlogn)O(n+knlogn)O(n+knlogn) 。

解题思路 由于解密只能一关关进行，而战斗只需要关卡解密已完成就可进行，因此问题简化为： 选择k关（x1⋅⋅⋅xkx_1 \cdot\cdot\cdot x_kx1 ⋅⋅⋅xk ），求∑i=1kxi\sum_{i=1}^{k} x_i∑i=1k xi 加上xkx_kxk 在解密时间上的前缀和的最小值。 建立前缀和数组sss存储解密时间前缀和，ttt数组用于存储每关的战斗时间（代码中为t_），sumsumsum变量用于存储堆中可能为最优的k关战斗时间和（代码中为sum_)，ansansans变量用于储存当前最优解（代码中为ans_）。 先把前k关战斗时间加入sumsumsum变量和优先队列pqpqpq，此时最优解可表示为ans=s[k]+sumans = s[k]+sumans=s[k]+sum。遍历接下来每一关，若其战斗时间小于当前队列中最大战斗时间，则可能成为最优解选择关卡之一，将其与最大时间交换，若新时间的确较原先最优解更优，更新ansansans。 遍历完所有关卡后，ansansans即为最优解。 实际代码