CF797E - Click Here
Description
$a$ is an array of $n$ positive integers, all of which are not greater than $n$.
You have to process $q$ queries to this array. Each query is represented by two numbers $p$ and $k$. Several operations are performed in each query; each operation changes $p$ to $p + a_p + k$. There operations are applied until $p$ becomes greater than $n$. The answer to the query is the number of performed operations.
Input
The first line contains one integer $n$ ($1 \leq n \leq 100000$).
The second line contains $n$ integers — elements of $a$ ($1 \leq a_i \leq n$ for each $i$ from 1 to $n$).
The third line containts one integer $q$ ($1 \leq q \leq 100000$).
Then $q$ lines follow. Each line contains the values of $p$ and $k$ for corresponding query ($1 \leq p, k \leq n$).
Output
Print $q$ integers, $i$th integer must be equal to the answer to $i$th query.
Solutions
在不考虑时间复杂度的情况下，我们可以得到两种做法。
一种是暴力计算操作次数，其时间复杂度为$O(\frac{n}{k})$
另一种是DP计算，设$f(i)$表示在$i$处需要的操作数，其时间复杂度为$O(n)$。
暴力计算的好处是，时间复杂度与$k$相关；DP计算的好处是，对于相同的$k$，能够$O(1)$得知答案。
考虑平衡两种做法。首先对询问进行离线，按照$k$排序。
接着设定一个阀值$m$，当$k \leq m$时选择暴力，当$m \leq k$时选择DP。
根据均值不等式可得，$m$取$\sqrt q$时，能最小化总时间复杂度。
时间复杂度$O(n \sqrt q)$
CODE
CODE - Click Here