题目理解

游戏中有 $n$ 个敌人，分布在 $n+1$ 个地牢中。英雄从地牢 $x$ 出发，初始能力值为 $z$。在每一个地牢 $i$ 中：

• 如果英雄能力值 $\ge s[i]$：胜利，能力值增加 $s[i]$，前往地牢 $w[i]$（$w[i] > i$）
• 否则：失败，能力值增加 $p[i]$，前往地牢 $l[i]$

地牢 $n$ 是终点。给定 $q$ 次询问 $(x, z)$，需要计算游戏结束时英雄的能力值。

---

关键观察

1. 能力值增长特性

英雄的能力值只增不减，且每次至少增加 $1$。游戏保证在有限步内结束。

2. 胜利边的特性

$w[i] > i$ 意味着胜利总是向前（向编号更大的地牢）移动，这保证了游戏的有向无环性。

3. 分阶段倍增思想

能力值会不断增长，可以按照能力值的不同范围将游戏分为多个阶段。在每个阶段内，敌我的强弱关系相对稳定，可以使用倍增加速模拟。

---

算法设计

1. 能力值分阶段

设 $B = 64$，将能力值划分为 $5$ 个区间：

• 阶段 $0$：$[1, B)$
• 阶段 $1$：$[B, B^2)$
• 阶段 $2$：$[B^2, B^3)$
• 阶段 $3$：$[B^3, B^4)$
• 阶段 $4$：$[B^4, \infty)$

对于每个阶段 $bl$，假设当前能力值 $y < B^{bl+1}$，可以预计算在该阶段内的胜负情况。

2. 预处理倍增数组

对于每个阶段 $bl$，预处理三个数组：

• f[bl][i][j]：从地牢 $i$ 出发，走 $2^j$ 步后到达的地牢
• g[bl][i][j]：从地牢 $i$ 出发，走 $2^j$ 步后能力值的总增加量
• h[bl][i][j]：从地牢 $i$ 出发，走 $2^j$ 步所需的能力值上限

初始化规则：

• 若 $s[i] < B^{bl}$：按胜利处理（前往 $w[i]$，增加 $s[i]$）
• 否则：按失败处理（前往 $l[i]$，增加 $p[i]$）

h[bl][i][0] 需要确保在当前能力值下假设成立：

• 若 $s[i] < B^{bl}$：上限为 $B^{bl+1} - 1$
• 若 $s[i] \in [B^{bl}, B^{bl+1})$：上限为 $s[i] - 1$
• 否则：上限为 $B^{bl+1} - 1$

3. 查询处理

ll simulate(int x, int z) {
    return ask(get(z), x + 1, z);
}

ask(bl, x, y) 函数：

1. 在当前阶段 $bl$ 内进行倍增跳跃
2. 若不能再跳，则实际模拟一步
3. 更新能力值和阶段，递归处理

---

算法正确性

1. 阶段划分的合理性

能力值单调递增，且增长迅速。划分为 $5$ 个阶段足以覆盖所有可能的能力值范围（最大约 $10^7 + 4 \times 10^5 \times 10^7 \approx 4 \times 10^{12}$）。

2. 倍增假设的保守性

h 数组确保了在跳跃过程中，实际的能力值永远不会超过假设的胜负界限。一旦可能超过，就停止跳跃，转为单步模拟。

3. 递归终止性

每次递归调用时，要么到达终点，要么能力值增长导致阶段提升。阶段最多提升 $5$ 次，且每次阶段内最多进行 $O(\log n)$ 次跳跃，因此总步数有限。

---

复杂度分析

时间复杂度

• 预处理：$O(5 \times n \log n)$
  • 5个阶段，每个阶段预处理 $n$ 个点的倍增数组，层数 $O(\log n)$
• 每次查询：$O(5 \times \log n)$
  • 最多经历 5 个阶段，每个阶段最多进行 $O(\log n)$ 次跳跃

对于 $n \leq 4 \times 10^5$，$q \leq 5 \times 10^4$，总复杂度大约为 $10^8$ 级别，可以接受。

空间复杂度

• f 数组：$5 \times n \times 20$ 个 int
• g 和 h 数组：$5 \times n \times 20$ 个 long long 总空间约 $5 \times 4 \times 10^5 \times 20 \times (4 + 8 + 8) / 1024 / 1024 \approx 763$ MB，在 2048 MB 限制内。

---

实现细节

1. 数组定义

int f[5][N][20];      // 跳跃目标
ll g[5][N][20];       // 能力值增量
ll h[5][N][20];       // 能力值上限
ll pw[6];             // 阶段边界 B^0, B^1, ..., B^5

2. 阶段判断函数

int get(ll y) {
    for (int i = 0; i < 5; i++)
        if (y < pw[i + 1])
            return i;
}

3. 主查询函数

ll ask(int bl, int x, ll y) {
    // 倍增跳跃
    for (int i = 19; ~i; i--)
        if (y <= h[bl][x][i])
            y += g[bl][x][i], x = f[bl][x][i];
    
    // 到达终点
    if (x == n + 1) return y;
    
    // 单步模拟
    if (y >= s[x])
        y += s[x], x = w[x];
    else
        y += p[x], x = l[x];
    
    // 到达终点或进入下一阶段
    if (x == n + 1) return y;
    return ask(get(y), x, y);
}

---

算法优势

1. 自适应阶段

算法根据当前能力值自动选择合适的倍增表，避免了为所有可能的能力值预计算。

2. 安全保证

通过 h 数组确保跳跃的安全性，只有在假设成立的情况下才进行跳跃。

3. 代码简洁

核心逻辑清晰，预处理和查询分离良好。

---

算法标签

• 倍增法
• 递推
• 模拟
• ST表

---

总结

本题通过巧妙的阶段划分和倍增预处理，将看似需要逐步模拟的过程优化到对数级别。关键在于观察到能力值的增长会使敌我强弱关系趋于稳定，从而可以在每个阶段内进行批量跳跃。算法在时间和空间复杂度之间取得了良好平衡，能够处理大规模数据。