跳跃次数查询根号分治

这是 baozii 佬的废稿，我觉得很有意思所以做个记录，另外这是我第一次接触根号分治这种算法 ~~不在提高组的大纲里我不会，那不是很正常~~。

题意#

给定一个长度为 $n$ 的数组 $a_i$ （ $1\le a_i\le n$ ），然后有 $q$ 个查询。

对于每个查询，给定 $i$ 与 $k$ ，然后重复执行 $i=i+a_i+k$ ，直至 $i\gt n$ ，求执行次数。

$1\le n,q,k\le 10^5$

题解#

发现对于暴力算法，当 $a_i$ 与 $k$ 为一个很小的数字时，整体复杂度为 $O(n^2)$ （ $n,q,k$ 同阶），显然超时。

如果我们预处理对于每个 $i,k$ 的答案 $ans_{i,k}$ 呢？首先 $O(n^2)$ 的预处理还是会超时，其次开不出来 $nk=10^{10}$ 的数组。

结合上面两种思想，考虑分治。对于 $k\ge\sqrt{n}$ ，每次暴力查询的最大复杂度为 $O(\sqrt n)$ ，这时暴力是可行的，对于 $k \lt \sqrt n$ ，预处理 $ans_{i,k}$ 的复杂度 $O(n\sqrt k)$ 可以接受。最终时间复杂度为 $O(n\sqrt n)$ 。