到达终点的跳跃次数（有更新）

Question

我们有 N 个方格，编号为 0 到 N - 1。每个方格都有目标跳跃方格 J[i]（必须位于较大的索引处）。在 i 方格，只能跳到 J[i] 方格。如果 J[i] 超过了最后一个方格，那么你就完成了。

我们一开始就知道所有 J[i]，然后我们有 Q 个查询。如果更新查询，它会将 J[i] 更改为特定的 i（仍然满足 J[i] > i）。其他类型的查询询问从给定的方格开始到经过最后一个方格（N-1）需要多少次跳跃。

Constraints:
1 <= N, Q <= 100,000
i + 1 <= J[i] <= 1,000,000

Example:
Jump squares: 
[1, 3, 3, 5]
Get answer fro square 1: 1 -> 3 -> 5 [past end] (2 jumps)
Update square 2's jump square (J[2]) to 4
Get answer for square 2: 2->4 [past end] (1 jump)

我尝试使用 dp（动态编程）来存储每个方块的跳跃次数，但是更新使我的解决方案速度减慢太多，因为我必须更新可能所有方块的 dp 答案。

static int[] dp;

static int getjump(int square, int[] jumpSquares) {
    if (square >= dp.length) return 0; // past end
    if (dp[square] != -1) return dp[square]; // already calc
    return dp[square] = 1 + getjump(jumpSquares[square], jumpSquares); // do one jump and check
}

static List<Integer> solve(int n, int[] jumpSquares, int[][] queries) {
    dp = new int[n];
    for (int i = 0; i < n; i++) dp[i] = -1;
    List<Integer> answers = new ArrayList<Integer>();
    for (int[] qq : queries) {
        if (qq.length == 1) {
             answers.add(getjump(qq[0], jumpSquares));
        } else { // update
             jumpSquares[qq[0]] = qq[1];
             for (int i = 0; i <= qq[0]; i++) dp[i] = -1; 
             // reset answers that might depend on updated square (qq[0])
        }
    }
    return answers;
}

如何更有效地解决这个问题（比 O(N*Q) 更好）？

Answer 1

我不确定这是否可以通过算法上比

O(n*q)

更简单的方式轻松解决。我们必须找到一条艰难的路。

将问题可视化，每个方格都有一个指向其他方格的箭头。仅仅跟随每个箭头太慢（可能需要多达 100k 个“箭头跟随”just 来处理单个查询），但是记忆答案意味着可能需要 100k 个步骤 just 来更新/使记忆无效，这是也太慢了。

我们可以使一个查询变快，但这会使另一个查询变慢。

我们需要一些额外的东西来实现这一点；基本规则似乎注定我们会采用

O(n*q)

算法。

所有跳跃都向前进行的规则是关键的额外辅助事实。我们可以将问题分成几个部分：不要记住“到达终点”需要多少步骤，而是记住到达下一个部分需要多少步骤，我们将每个部分定义为例如是316个正方形。换句话说，我们将正方形 id 分成 317 个部分，每个部分有 316 个正方形大。段 0 是 0-315，段 1 是 316-631，等等（选择 316 因为它是

SQRT(100_000)

）。

换句话说，不要死记硬背“从 58 号方格到终点需要 20 步”，例如：

memoization[58] = 20

，您可以记住方格 58“需要 8 步才能到达方格 325”，其中 325 是当您从 58 开始步行时“碰到”的下一段中的第一个方格。这确实意味着您现在需要存储 2 个数字（

8

和

325

），但如果你真的想优化，100_000 * 317 只是 31600000 并且适合 int （换句话说，你可以压缩 'square I end up at' 和 '如果必须的话，这将采取的步骤数为单个 4 字节 int 数字）。

有了这个系统，计算出“需要多少步才能到达终点”查询需要

O(sqrt(n))

步，而不是

O(n)

步。你仍然像平常一样沿着树走，但每一步都保证让你前进至少 1 段，而且只有 317 段，所以最坏的情况只是 317（n 的平方根）。

更新查询也最多只需要 sqrt(n) 步。任何引导到更新的方块的跳跃方块都不需要更新如果“源”方块位于下段。毕竟，您可以保证记忆的跳转结束在更新的方块（或更早）中，这很好。唯一可能需要更新记忆的方块是同一段中跳过更新方块的任何方块。计算出这一点同样受到

O(sqrt(n))

的限制，因为您永远不必检查超过 316 个源方格。为了有效地检查、向后走或记住经过该方格的方格列表（该列表最多可以包含 316 个条目；为每个方格创建一个 316 大小的数组需要 126MB；很大，但可行）。我将把如何有效地做到这一点作为练习留给读者。