数组跳跃查询 题解

思路

当 $k$ 大时，每步至少前进 $k+1$，可直接模拟；当 $k$ 小时，为每个 $k$ 预处理从每个位置出界所需步数。

做法

子任务 1

逐查询模拟跳跃，复杂度 $O(nq)$。

子任务 2

因为 $k\ge320$，每个查询至多进行 $O(n/320)$ 次操作，直接模拟。

子任务 3

取阈值 $B=320$。对每个 $k<B$，从后向前计算

越界状态为 0。小 $k$ 查询直接读取，大 $k$ 查询模拟。

正确性证明

引理 1 递推式准确给出固定 $k$ 时从位置 $p$ 出界的步数。

证明 第一次操作唯一到达 $p+a_p+k$，其后剩余步数正是该位置的 DP 值。∎

引理 2 两类查询都被正确处理。

证明 小 $k$ 由引理 1 读取正确预处理值；大 $k$ 完整模拟题目定义，直到首次出界。∎

定理 算法对每个查询输出正确操作次数。∎

复杂度

时间复杂度 $O(nB+q n/B)$，空间复杂度 $O(nB)$。