1. 问题形式化描述

我们有一个无限长的数轴，起点为位置 $0$。目标是通过两种操作到达指定的目标位置 $X_j$：

操作1（走步）：从位置 $p$ 移动到 $p+1$，花费 $A$ 时间

操作2（跳跃）：从位置 $p$ 移动到 $p+D$，花费 $B$ 时间

存在 $N$ 个禁止区间 $[L_i, R_i]$，表示这些位置不可停留。要求计算到达每个 $X_j$ 的最短时间，或判断不可达。

2. 基础观察与难点

关键难点：

数据规模巨大：$X_j, L_i, R_i$ 可达 $10^{12}$，无法直接处理整个数轴

跳跃操作引入长距离依赖，使得局部性分析困难

禁止区间形成障碍，需要绕行策略

重要性质：

禁止区间互不相交且按升序排列（$R_i + 1 < L_{i+1}$）

只能向上移动，具有单调性

操作代价与位置无关，只与操作类型相关

3. 无禁止区间的最优策略分析

在没有禁止区间的情况下，问题简化为经典的硬币找零问题变种。设目标位置为 $x$：

令 $k = \lfloor x/D \rfloor$，$r = x \bmod D$

基础策略：进行 $k$ 次跳跃和 $r$ 次走步，总时间 $k \times B + r \times A$

最优性分析：

如果 $B < D \times A$，跳跃总是优于连续走步

如果 $B > D \times A$，应尽量减少跳跃次数

但由于只能向上移动，实际上最优策略就是上述基础策略

4. 禁止区间的影响机制

禁止区间对两种操作产生不同影响：

对走步的影响：

如果位置 $p$ 在禁止区间内，不能从 $p-1$ 走到 $p$

也不能从 $p$ 走到 $p+1$

对跳跃的影响：

从 $u$ 跳跃到 $u+D$ 时，中间经过的位置 $u+1, u+2, \ldots, u+D-1$ 不能有任何禁止点

等价条件：区间 $(u, u+D)$ 与任何禁止区间 $[L_i, R_i]$ 不相交

5. 关键点理论

由于数轴无限但关键事件有限，我们可以将问题离散化：

关键点集合 $S$ 包含：

起点：$0$

禁止区间边界：$L_i - 1$（区间前最后一个安全位置），$R_i + 1$（区间后第一个安全位置）

目标位置：$X_j$

跳跃相关点：对于每个 $s \in S$，考虑 $s - D$ 和 $s + D$（如果非负且在合理范围内）

关键性质：

任何最优路径只会在关键点处改变移动策略

在相邻关键点之间，移动策略是确定的

复杂度分析：

顶点数：$O(N + Q)$

边数：每个顶点最多 2 条出边

总复杂度：$O((N + Q) \log(N + Q))$