观察可以发现一个结论，可以视作每个点 \(i\) 可以一步到达 \(l_i \sim n\) 的每一个点。
发现对于 \(a< b<x\)，\(dist(a, x) \ge dist(b, x)\)
第一步是相当特殊的，因为第一步的起点是一个点，而之后的每一步都可以视作从这一段中的任意点出发
于是我们特殊处理第一步，然后将第二步当作第一步
那么，新的第一步是从 \(l_{x}\sim n\) 的任意一个点出发
第二步是从 \(\min_\limits{k\ge l_x}\{l_k\} \sim n\) 的任意一个点出发
于是可以考虑倍增
\(f_{i, j}\) 表示从 \(j\sim n\) 的任意一个点出发，走 \(2^i\) 步能到达的最靠左的点
那么，走 \(2^i\) 步能到达 \(f_{i,j} \sim n\) 的每一个点
于是我们可以得到转移
\[f_{i, j} = f_{i-1, f_{i-1,j}} \]初始条件为
\[f_{0,j}=\min_{k\ge j}\{l_k\} \]那么我们用 \(g_{i,j}\) 表示从 \(j\sim n\) 的任意一个点出发，到 $f_{i,j} \sim j- 1 $ 的最短步数之和
\[g_{i,j} = g_{i-1,j}+2^{i-1}(f_{i-1, j}-f_{i,j}) + g_{i-1,f_{i-1,j}} \]初始条件为
\[g_{0,j} = j - f_{0,j} \]计算时倍增即可，注意加上之前被忽略的第一步。
#include <bits/stdc++.h>
using namespace std;
int n, l[300005];
int q, a, b, x;
int f[25][300005];
long long g[25][300005];
long long query(int a, int x) {
int now = l[x];
if (now <= a) return x - a;
long long ans = 0;
for (int i = log2(n); i >= 0; i--) {
if (f[i][now] >= a) {
ans += g[i][now];
now = f[i][now];
ans += 1ll * (now - a) * (1ll << i);
}
}
ans += now - a;
return ans + (x - a);
}
int main() {
scanf("%d", &n);
l[1] = 1;
for (int i = 2; i <= n; i++) {
scanf("%d", l + i);
}
for (int i = n, minx = 0x7fffffff; i >= 1; i--) {
minx = min(minx, l[i]);
f[0][i] = minx;
g[0][i] = i - f[0][i];
}
for (int i = 1; i <= log2(n); i++) {
for (int j = 1; j <= n; j++) {
f[i][j] = f[i - 1][f[i - 1][j]];
g[i][j] = g[i - 1][j] + g[i - 1][f[i - 1][j]] + (1ll << (i - 1)) * (f[i - 1][j] - f[i][j]);
}
}
scanf("%d", &q);
while (q--) {
scanf("%d%d%d", &a, &b, &x);
long long ans = query(a, x) - query(b + 1, x), len = b - a + 1;
long long gcd = __gcd(ans, len);
printf("%lld/%lld\n", ans / gcd, len / gcd);
}
return 0;
}