题目大意

有一只青蛙在 (n)，在点 (i) 可以向上跳最多 (a[i]) 的距离，跳完之后若在 (j) 点，当前位置则会变为 (j+b[j])

这个做法是 xmz 教给我的

题解

显然可以转化为一个图论问题，然后区间加边求单源最短路，需要 DS 优化建图。

但这个东西比较复杂，这里介绍一种简单的图论做法。

我们考虑我们上述问题的复杂度瓶颈是什么，就是在每个点都会扫一遍全部出边，这很有可能让复杂度退化到 (O(n^2))。但考虑到这些点中有一些是我们已经扫过的，显然再遍历一遍肯定不如上一次的答案优秀，如果能够去掉这些点复杂度就能降下来。

观察可得，已经扫过的点肯定是呈现为一个区间，所以我们可以借用树上冰茶姬覆盖的想法来维护这个东西。

具体来说每个点维护一个冰茶姬，当扫过 (i) 点之后，就将它的前驱 (i+1) 和自己 (unite) 起来，这样就可以很方便的维护出下一个未覆盖的点是谁。

我自己实现的时候冰茶姬似乎只能路径压缩，不能按秩合并。所以复杂度也只能做到 (O(nlog n))