题解：分批操作的向前弹跳¶
出题人解法：维护答案后缀，按需从高位置向低位置重算。Codex（GPT-6）补齐正弹力与分批保证的精确定义，整理实现并给出复杂度证明；另提供应用标准 Link-Cut Tree 的动态树方案。
只维护已经需要的后缀¶
正弹力保证 \(i+K_i>i\) .令 \(f_i\) 为从垫子 \(i\) 出发的答案，则
从大到小计算即可。维护边界 \(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\) ，而不是把一般输入也当成常数时间。
- 以 \(h+1\) 为势能，重算一次使它减少一；一次修改最多增加 \(A+1\) .所以 \(R\le n+1+\sum(A+1)\) .第一组的修改位置总和受限，总修改次数也不超过 \(q\) .
- 第二组的修改形成至多110个连续段：100个选定区间，加上至多10次额外修改。每段后的所有连续查询最多重算 \(n+1\) 个位置，开头可能另有一段查询，故 \(R\le111(n+1)\) .
- 第三组同理至多110个询问段。段内没有修改，边界只下降，所以 \(R\le110(n+1)\) .
- 设局部区间数为 \(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\) .
标准程序采用出题人方法。动态树方案与程序用 \(O(\log n)\) 摊还时间处理任意单次操作，具有不依赖分批形状的理论保证；本题正式数据上常数开销更大，最慢约3.50秒，超过按标准程序校准的0.5秒限制，作为更一般输入下的取舍方案保留。标准程序最慢约0.20秒。