我的思路

如果没有修改就是一个简单的DP

其他

这是一个典型的可以使用分块思想解决的问题。问题的核心在于，如果直接模拟绵羊的跳跃过程，最坏情况下每次只跳一步，一次查询的时间复杂度可能是 $O(N)$，总时间复杂度为 $O(NM)$，无法通过大数据。我们需要一种方法来加速跳跃的过程。

分块思路

我们将 $N$ 个装置分成 $\sqrt{N}$ 个块，每个块的大小 $B \approx \sqrt{N}$。

对于每个装置 $i$，我们预处理出两个信息：

1. step[i]：从装置 $i$ 开始跳，需要跳多少步才能跳出当前所在的块。
2. to[i]：从装置 $i$ 开始跳，跳出当前块后，第一次落在哪一个位置。如果直接跳出了所有装置的范围（即位置 $\ge N$），这个值就是那个跳出范围的位置。

预处理： 我们可以从最后一个装置 $N-1$ 开始往第一个装置 $0$ 遍历，计算每个装置的 step 和 to 值。对于装置 $i$，它的下一次跳跃位置是 $target = i + k_i$。

• 如果 $target \ge N$ 或者 $target$ 所在的块不同于 $i$ 所在的块：说明从 $i$ 跳一步就出了当前块。
  • step[i] = 1
  • to[i] = target
• 如果 $target < N$ 且 $target$ 与 $i$ 在同一个块内：说明跳到 $target$ 后还在当前块，那么从 $i$ 跳出块的步数等于从 $target$ 跳出块的步数加 1，跳出块后的落点也与从 $target$ 出发相同。
  • step[i] = step[target] + 1
  • to[i] = to[target] 由于我们是从右往左计算的，当计算 $i$ 时，$target$ 的信息已经计算好了。预处理的时间复杂度为 $O(N)$。

查询操作（Type 1）： 询问从 $j$ 出发需要跳几次。 我们维护当前位置 curr，初始为 $j$，总步数 ans 初始为 0。 只要 curr < N，我们就利用预处理的信息进行快速跳跃：

• ans += step[curr]：加上跳出当前块所需的步数。
• curr = to[curr]：直接跳到下一个块的落点（或超出 $N$ 的位置）。 每次操作至少跳过一个块，最多需要跳过 $N/B$ 个块。查询的时间复杂度为 $O(N/B) = O(\sqrt{N})$。

修改操作（Type 2）： 修改装置 $j$ 的弹力系数为 $k$。 这个修改只会影响 $j$ 所在的块内，且在 $j$ 及其左侧的装置的 step 和 to 值。我们只需要重新计算 $j$ 所在块内的所有装置的信息即可。计算顺序依然是从块的右边界向左边界进行。 修改的时间复杂度为 $O(B) = O(\sqrt{N})$。

总时间复杂度： 总时间复杂度为 $O(N + M\sqrt{N})$。给定数据范围 $N \le 2 \times 10^5, M \le 10^5$，$\sqrt{N} \approx 450$，计算量约为 $4.5 \times 10^7$，可以在时限内完成。

C++ 代码实现

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

const int MAXN = 200005;
int n, m;
int k[MAXN];        // 弹力系数
int step[MAXN];     // 跳出当前块的步数
int to[MAXN];       // 跳出当前块后的落点
int block_id[MAXN]; // 每个位置所属的块编号
int B;              // 块大小

// 更新特定块的信息
void update_block(int b) {
    int start = b * B; // 块的起始位置
    int end = min(n - 1, (b + 1) * B - 1); // 块的结束位置
    // 从右向左更新
    for (int i = end; i >= start; --i) {
        int target = i + k[i];
        // 如果跳出了边界或者跳到了下一个块
        if (target >= n || block_id[target] != b) {
            step[i] = 1;
            to[i] = target;
        } else {
            // 如果还在同一个块内，利用 target 的信息
            step[i] = step[target] + 1;
            to[i] = to[target];
        }
    }
}

int main() {
    // 优化 I/O 速度
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    B = sqrt(n); // 设置块大小
    // 处理 N=0 的边界情况，虽然题目保证是正整数，但在通用分块模板中要注意
    if (B <= 0) B = 1; 

    for (int i = 0; i < n; ++i) {
        cin >> k[i];
        block_id[i] = i / B; // 计算所属块编号
    }

    // 初始预处理，计算所有点的 step 和 to
    for (int i = n - 1; i >= 0; --i) {
        int target = i + k[i];
        if (target >= n || block_id[target] != block_id[i]) {
            step[i] = 1;
            to[i] = target;
        } else {
            step[i] = step[target] + 1;
            to[i] = to[target];
        }
    }

    cin >> m;
    while (m--) {
        int type;
        cin >> type;
        if (type == 1) { // 查询操作
            int j;
            cin >> j;
            int ans = 0;
            int curr = j;
            // 不断跳出当前块，直到跳出所有装置
            while (curr < n) {
                ans += step[curr];
                curr = to[curr];
            }
            cout << ans << "\n";
        } else { // 修改操作
            int j, new_k;
            cin >> j >> new_k;
            k[j] = new_k;
            // 只需更新 j 所在的块
            update_block(block_id[j]);
        }
    }

    return 0;
}

总结

这个题目用分块,真是太巧妙了,尤其是修改操作

修改操作（Type 2）：
修改装置 $j$ 的弹力系数为 $k$。
这个修改只会影响 $j$ 所在的块内，且在 $j$ 及其左侧的装置的 step 和 to 值。我们只需要重新计算 $j$ 所在块内的所有装置的信息即可。计算顺序依然是从块的右边界向左边界进行。
修改的时间复杂度为 $O(B) = O(\sqrt{N})$。

我所理解的分块,就是用来, 维护区间信息的, 比如区间和. 但是这个维护了什么区间信息?

是不是只要维护的区间信息,不影响其他区间的信息,就可以使用分块?

你的直觉非常敏锐！这两个问题问到了分块思想的精髓。

这个题目中分块的应用确实非常巧妙，它和我们平时最常见的“维护区间和”、“区间最大值”那种分块很不一样。

让我们来深入拆解一下你的疑虑。

1. 这个分块到底维护了什么“区间信息”？

你习惯的分块可能是这样的：把数组分成若干块，每个块维护一个 sum 值。查询时，整块加 sum，散块暴力加。

但在这个题目里，块并没有维护一个单一的整体信息（比如这个块的总弹力是多少，并没有意义）。

它维护的“区间信息”，实际上是一种“路径压缩”或者叫“过程加速”的信息。

具体来说，对于块内的每一个点 $i$，它维护的信息是： “如果绵羊跳到了这个点 $i$，在它最终跳出这个块之前，它在这个块内一共要跳几次 (step[i])，以及跳出块后的第一个落点在哪里 (to[i])。”

这就好比走迷宫。我们把迷宫分成了若干个房间（块）。

• 普通的分块可能是统计每个房间里有多少宝藏。
• 而这道题的分块，是在预处理：如果你从这个地砖进入这个房间，你最终会从哪个门离开这个房间，并且需要在房间里走几步。

我们将块内复杂的多次小跳跃，压缩成了“一次”大跳跃（直接跳出块）。

总结：这里的“区间信息”不再是数据的简单聚合（Sum/Max），而是对一段局部过程（在块内跳跃）的模拟结果的缓存。

2. 是不是只要维护的区间信息不影响其他区间，就可以用分块？

答案是肯定的。这是分块算法能够成立的核心前提，叫做“局部性原理”或者“信息的独立性”。

让我们看看为什么这个题目的修改操作满足这个前提：

我们修改了点 $j$ 的弹力系数 $k[j]$。

1. 对其他块有影响吗？

   • 没有。其他块的点跳出它们自己的块时，落点虽然可能在 $j$ 所在的块，也可能不在。但它们怎么跳出它们自己的块，只取决于它们自己块内的结构和跳出去的第一步落点。这与点 $j$ 的具体弹力值无关。

2. 对 $j$ 所在块内的其他点有影响吗？

   • 对 $j$ 右边的点： 没有影响。因为跳跃是往右跳的，$j$ 右边的点怎么跳出块，跟 $j$ 没关系。
   • 对 $j$ 左边的点： 有影响。 因为 $j$ 左边的点可能会跳到 $j$ 上。原来跳到 $j$ 上后，下一步去了 A 地；现在 $k[j]$ 变了，跳到 $j$ 上后，下一步去了 B 地。这会导致左边这些点的 step 和 to 发生变化。

关键点在于：这种影响传导到块的左边界就停止了。

这就是你注意到的那个巧妙之处：

“这个修改只会影响 $j$ 所在的块内……我们只需要重新计算 $j$ 所在块内的所有装置的信息即可。”

正是因为修改一个点的信息，只需要重建它所在的那个块，而不需要动其他的 $\sqrt{N}-1$ 个块，才使得修改操作的复杂度控制在了 $O(\sqrt{N})$。

总结与提升

你对分块的理解可以从“维护区间和”升级到更广义的层面了：

分块（Square Root Decomposition）本质上是一种平衡思想和一种对问题的划分策略。

1. 平衡思想： 暴力修改快 ($O(1)$)，查询慢 ($O(N)$)；或者某些数据结构查询快，修改慢。分块试图将修改和查询的复杂度都平衡到 $O(\sqrt{N})$ 级别。
2. 划分策略（核心）： 将大规模问题划分成若干个规模较小的子问题（块）。关键在于，需要设计一种信息维护方式，使得一个小块内部发生变化时，其影响范围被局限在这个小块内部，而不会扩散到整个数据集。

只要满足这个“影响局限性”，我们就可以利用分块的思想：

• 查询时： 跨越整块时利用预处理好的整块信息加速，利用散块信息精确调整。
• 修改时： 暴力重构受影响的那个小块。

这道弹飞绵羊的题目，就是利用分块隔离了“路径依赖”的影响范围，是非常经典且优雅的应用案例。