# 题解：分批操作的向前弹跳

出题人解法：维护答案后缀，按需从高位置向低位置重算。Codex（GPT-6）补齐正弹力与分批保证的精确定义，整理实现并给出复杂度证明；另提供应用标准 Link-Cut Tree 的动态树方案。

## 只维护已经需要的后缀

正弹力保证 $i+K_i>i$ .令 $f_i$ 为从垫子 $i$ 出发的答案，则

$$f_i=\begin{cases}1,&i+K_i>n\\1+f_{i+K_i},&i+K_i\le n\end{cases}$$

从大到小计算即可。维护边界 $h$ ，不变量是所有位置大于 $h$ 的答案都正确；不要求更小位置的缓存有效。初始 $h=n$ .

修改 $K_A$ 只可能影响位置不大于 $A$ 的答案，因此令 $h\gets\max(h,A)$ .询问 $C\le n$ 时，从 $h$ 向下重算到 $C$ ，再令 $h=C-1$ ；若原来 $h<C$ ，无需重算。每个计算依赖的下标都更大，因此依赖值已经正确。询问 $C>n$ 直接返回零，不改变缓存边界。

由初始状态、修改操作和下降重算的归纳，不变量始终成立，每个查询返回正确的 $f_C$ .

## 分批条件如何控制工作量

记总重算位置数为 $R$ ，算法总时间为 $O(n+q+R)$ ，空间为 $O(n)$ .下面说明每组的保证如何限制 $R$ ，而不是把一般输入也当成常数时间。

1. 以 $h+1$ 为势能，重算一次使它减少一；一次修改最多增加 $A+1$ .所以 $R\le n+1+\sum(A+1)$ .第一组的修改位置总和受限，总修改次数也不超过 $q$ .
2. 第二组的修改形成至多110个连续段：100个选定区间，加上至多10次额外修改。每段后的所有连续查询最多重算 $n+1$ 个位置，开头可能另有一段查询，故 $R\le111(n+1)$ .
3. 第三组同理至多110个询问段。段内没有修改，边界只下降，所以 $R\le110(n+1)$ .
4. 设局部区间数为 $s$ 、最大位置跨度为 $W$ .每段第一次查询最多补算整个数组；之后每次重算长度至多 $W+1$ ，因为修改和查询的位置都留在同一局部区间。因此 $R\le s(n+1)+q(W+1)$ ，本题 $s\le100,W\le500$ .

这些是上界，实际重算常会少很多。完全一般的操作序列可能达到 $O(nq)$ ，不能去掉分批保证后沿用性能结论。

## 输出和另一种方法

异或分组使用完整操作编号，而不是询问编号。所有查询答案至多 $n+1$ ，其总和用64位整数；更新后的目标位置仍可用32位有符号整数，因为 $i+K_i\le300000+10^9$ .

[标准程序](std.cpp)采用出题人方法。[动态树方案](solution-alternative.zh.md)与[程序](alternative.cpp)用 $O(\log n)$ 摊还时间处理任意单次操作，具有不依赖分批形状的理论保证；本题正式数据上常数开销更大，最慢约3.50秒，超过按标准程序校准的0.5秒限制，作为更一般输入下的取舍方案保留。标准程序最慢约0.20秒。

见[测试说明](tests/README.md)及[逐次测量](../../../docs/benchmark-R37.json)。