Readme

3534.Path-Existence-Queries-in-a-Graph-II

我们将所有的数按照从小到大的顺序排列之后，本题的问题就是：给出任意两点u<v，从u跳跃至v最少需要多少步？

不难发现，通过双指针，我们可以知道任意一点x能向右跳跃的最远位置y。事实上我们只需要关心{x,y}之间的路径，而不用在意x到其他可跳跃位置的路径。这是因为对于其他任何早于y的位置z，根据定义，必然也可以从x到z的一步跳跃。

因此，对于任意的query={u,v}，如果问能否用k步实现跨越，其实只需要考察k次上述定义的跳跃路径：u->x, x-y, y->z, ... 如果最终的位置能够超越v，那么答案就是肯定。反之，如果问{u,v}之间最少用多少步可以实现跨越，那么显然我们可以用二分搜值再验证，从而逼近最优解。

对于验证的过程，我们如果线性地去模拟k次跳跃，时间是不够的。因此我们会用到binary lifting（倍增）算法。不仅计算x和它一步所能跳跃的最远点y之间的路径，而且还预处理up[x][k]，表示从x点往右跳跃2^k步所能到达的最远位置，其中k最大值是17即可。在准备好了up数组之后，二分搜值的验证过程只需要log(N)次的跳转即可。