题目解析

问题重述

Mualani 从位置 $1$ 出发，初始跳跃能力为 $1$，要到达位置 $L$。路上有 $n$ 个障碍区间 $[l_i, r_i]$（不能落在这些区间内），以及 $m$ 个强化道具（位于 $x_i$，价值 $v_i$，拾取后跳跃能力永久增加 $v_i$）。问最少拾取多少个道具才能到达终点，若不可能则输出 $-1$。

关键转化

$1$. 障碍物的处理

由于不能跳到障碍区间 $[l, r]$ 内的任何位置，Mualani 必须跨越这个区间。设她当前在位置 $p$（$p < l$），则她必须跳到 $\ge r+1$ 的位置。

最经济的跳法是：从 $p = l-1$ 跳到 $r+1$，需要的跳跃距离为：

因为起点是 $l-1$（障碍物前最后一个安全位置），终点是 $r+1$（障碍物后第一个安全位置），区间长度为 $r-l+2$。

$2$. 跳跃能力的含义

如果当前跳跃能力为 $k$，从位置 $x$ 可以跳到 $[x, x+k]$ 内的任意整数位置。要跨越一个障碍物，需要满足：

否则无法一次跳过。

$3$. 道具的收集策略

道具只能在其所在位置拾取。由于障碍物之间是分离的（$r_i+1 < l_{i+1}$），且道具不会出现在障碍区间内，因此道具只可能位于安全位置。

贪心策略

核心思想

遇到障碍物时，如果当前跳跃能力不足，就从之前经过的所有未被使用的道具中选择价值最大的拾取，直到能力足够。 这保证了每次跨越障碍物时使用的道具数量最少。

算法流程

$1$. 事件排序
将所有障碍物和道具按位置从小到大排序。同一位置时，道具优先于障碍物（因为先捡道具再处理障碍物更合理）。

$2$. 维护一个最大堆
堆中存储当前已遇到但尚未使用的道具价值。

$3$. 顺序处理事件

• 遇到道具（类型 $0$）：将其价值 $v$ 加入最大堆。
• 遇到障碍物 $[l, r]$：
  计算所需跳跃能力 $\text{need} = r - l + 2$。
  如果当前能力 $k < \text{need}$：
  循环从堆中取出最大价值道具，累加到 $k$，并计数 $used\_count$，直到 $k \ge \text{need}$ 或堆为空。
  如果堆空后仍 $k < \text{need}$，则无法跨越该障碍，输出 $-1$。

$4$. 输出结果
如果所有障碍都能跨越，输出 $used\_count$（即实际拾取的道具数量）。

时间复杂度

• 排序：$O((n+m)\log(n+m))$
• 每个道具最多入堆一次、出堆一次：$O((n+m)\log m)$
• 总复杂度：$O((n+m)\log (n+m))$，满足 $2\times 10^5$ 的数据范围。

正确性证明

引理 $1$：跨越障碍物时，使用当前遇到的最大价值道具是最优的。
证明：因为道具价值只影响跳跃能力，且能力需求是线性的。在必须增加相同总能力的情况下，选择价值最大的道具可以使拾取数量最少（等价于“用最少的物品凑够总价值”的贪心，由于价值无上限且可拆分，直接取最大即可）。

引理 $2$：先遇到的障碍物优先处理，且道具不会“过期”。
证明：由于障碍物按顺序出现，且道具只能在其位置之后使用（不能回到过去），所以遇到障碍物时，只有之前位置的道具可用。按时间顺序处理保证了这一点。

因此，该贪心策略得到全局最优解。

示例验证（第一个测试用例）

障碍物：$[7,14]$$（need = 14-7+2=9）$，$[30,40]$$（need = 40-30+2=12）$
道具：$(2,2), (3,1), (3,5), (18,2), (22,32)$

初始 $k=1$，遇到道具依次加入堆：$2,1,5$（堆中为 $5,2,1$）。
遇到第一个障碍 $need=9$，当前 $k=1<9$，取最大 $5$ → $k=6$，取 $2$ → $k=8$，取 $1$ → $k=9$，共取 $3$ 个道具。
继续遇到 $(18,2)$ 入堆，$(22,32)$ 入堆（堆中 $32,2$）。
遇到第二个障碍 $need=12$，当前 $k=9<12$，取 $32$ → $k=41$，取 $1$ 个道具。
总共取 $3+1=4$ 个道具，与样例输出一致。

注意事项

• 障碍物区间是闭区间 $[l, r]$，跨越必须到 $r+1$。
• 初始位置是 $1$，终点是 $L$，如果 $L$ 在障碍物内则不可达（但题目保证 $l_i \ge 2$，$r_i \le L-1$，所以终点安全）。
• 同位置有多个道具时，排序保证它们按顺序被处理。
• 堆中可能剩余未使用的道具，无需处理，因为不需要额外拾取。