【PKUSC2018】星际穿越
倍增
题目大意：
给定 $n$ 个点，第 $i(i>1)$ 个点有 $l_i$，表示点 $i$ 与 点 $l_i\sim i-1$ 之间的所有点都有一条权值为 $1$ 的边。
现在有 $q$ 组询问，每组询问给定 $L,R,x$，表示询问从 $[L,R]$ 中等概率选择一个点，$x$ 走到这个点的最短路的期望大小。
题解：
这个期望就是求个和再除以 $R-L+1$。
我们对第 $i$ 个点，令 $mn_i=\min_{j=i}^n l_j$.
我们求 $x$ 到 $y$ 的最短路时（$x>y$），每次（除了第一次和最后一次）肯定从当前的 $k$ 走到 $[l_k,k-1]$ 中 $l_p$ 最小的结点 $p$，这样可以令下一次能够走的越远。
最后一次当然直接走到 $y$，那么第一次呢？
有一种办法是，从 $x$ 向后走一格，然后再向前走，这样可能比 $x$ 向前走两格更远。
那么我们考虑 $mn_x$ 的意义，就是以 $x$ 作为出发点时，走两步能走到的最远的点。
那么不是出发点的时候呢？
令能一步走到 $mn_x$ 的那个点为 $a$，那么如果当前的 $x$ 不是出发点，就说明出发点在 $a$ 的更后面，则一定能保证，某一次最远能走到 $x$ 的同时，也一定能走到 $a$。那么再多一次，最远能走到的点，就是从 $a$ 走到 $mn_x$ 了。
所以说，如果 $x$ 不能一次走到 $y$，那么 $x$ 肯定是不断变为 $mn_x$，最后到达 $y$。
那么考虑倍增，令 $f[i][k]$ 表示点 $i$ 不是起点时走 $2^k$ 次能到达的最远的点，$f[i][0]=mn_i$。
令 $g[i][k]$ 表示 $i$ 走到 $f[i][k]\sim i-1$ 所有点的最短步数之和。
预处理的时候，可以通过 $k-1$ 的值递推出 $k$ 的值。
查询的时候，由于答案满足可减性，对后缀进行倍增查询即可。注意要先计算掉开始花一步就能走到的点的贡献。
时间复杂度 $O((n+m)\log n)$。
Code：
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N=300005;
int n,q,f[N][19],L[N],mn[N],d[N<<2];
LL g[N][19];
LL solve(int x,int k){
if(L[x]<=k)return x-k;
LL ret=x-L[x];x=L[x];
int s=1;
for(int i=18;~i;--i){
if(f[x][i]>=k){
ret+=(LL)s*(x-f[x][i])+g[x][i];
s+=1<<i;
x=f[x][i];
}
}
return ret+(s+1)*(x-k);
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n;
for(int i=2;i<=n;++i)
cin>>L[i];
mn[n]=L[n];
for(int i=n-1;i;--i)
mn[i]=min(L[i],mn[i+1]);
for(int i=1;i<=n;++i)
f[i][0]=mn[i],g[i][0]=i-mn[i];
for(int j=1;j<19;++j)
for(int i=1;i<=n;++i){
f[i][j]=f[f[i][j-1]][j-1];
g[i][j]=g[i][j-1]+g[f[i][j-1]][j-1]+(1LL<<j-1)*(f[i][j-1]-f[i][j]);
}
cin>>q;
while(q--){
int l,r,x;
cin>>l>>r>>x;
LL A=solve(x,l)-solve(x,r+1),B=r-l+1,g=__gcd(A,B);
cout<<A/g<<'/'<<B/g<<'\n';
}
return 0;
}