被 scb 神仙教育来扫荡北大营题目 Orz
Description
Solution
首先有个很显然的性质，就是对于一组询问 (l,r,x)，从 (x) 到 ([l,r]) 的最短距离 一定是从 (x) 一直向左走 或者从 (x) 向右走 (1) 单位时间然后一直向左走。
向右走 (1) 单位时间到达的位置是 (L_i) 最小的 (i)。如果 (min{L_i}ge L_x) 那就不用考虑向右走一步的情况了，否则在 (min{L_i}lt L_xlt x) 的限制下，我们可以从 (x) 一步到 (i)。
然后 (70) 分做法就很显然了，从每个点出发，模拟上面两个情况即可。
code （我之前把 (q) 也看成 (5000) 了，所以 T 了好几发）
以上过程看起来可以倍增优化，然后就开始学习倍增转移技巧
首先不分开考虑向右走和不向右走两种情况，我们在查询时先强制从 (x) 向左走一次，然后再往前倍增走即可，画图可知这样两种情况就合一了。此时我们不用考虑向右走的情况了，但强制往左走一次后再往左走到的位置 就要取位置 ([x,n]) 中所有 (L_i) 的最小值，因为可能是从 ((x,n]) 中某个位置走来的，即之前从 (x) 往右走了一步（如果 (L_x) 最小就无视这一步）。
然后根据一开始说过的性质，最优答案最多只在一开始位于 ((x,n]) 之间的位置，以后不会闲的蛋疼再回到那些位置，故一直顺带记录那些位置能到达的最左位置 不会影响找到最优解。
这样代码就好实现了：预处理 (to(i,j)) 表示从 ([i,n]) 中任一位置向左走 (j) 个单位时间，最左可以走到哪个位置；再预处理 (sum(i,j)) 表示从 (i) 到 ([to(i,j),i)) 区间内所有位置的最短距离之和。
查询时倍增跑到询问区间 ([l,r]) 的左端点 (l) 即可。
详见代码。
#include<bits/stdc++.h>
#define ll long long
#define N 300001
using namespace std;
inline int read(){
int x=0; bool f=1; char c=getchar();
for(;!isdigit(c); c=getchar()) if(c=='-') f=0;
for(; isdigit(c); c=getchar()) x=(x<<3)+(x<<1)+(c^'0');
if(f) return x;
return 0-x;
}
int n,q,L[N],to[20][N]; ll sum[20][N];
ll gcd(ll x, ll y){
ll t;
while(y) t=x, x=y, y=t%y;
return x;
}
ll calc(int l, int r){
if(L[r]<=l) return r-l;
ll ans=r-L[r]; r=L[r]; int tot=1;
for(int i=19; ~i; --i) if(to[i][r]>l) ans+=sum[i][r]+(ll)tot*(r-to[i][r]), r=to[i][r], tot+=1<<i;
return ans+(ll)(r-l)*(tot+1);
}
int main(){
n=read(); L[1]=1;
for(int i=2; i<=n; ++i) L[i]=read();
to[0][n]=L[n], sum[0][n]=n-L[n];
for(int i=n-1; i; --i) to[0][i]=min(to[0][i+1],L[i]), sum[0][i]=i-to[0][i];
for(int i=1; i<=19; ++i)
for(int j=1; j<=n; ++j)
to[i][j] = to[i-1][to[i-1][j]],
sum[i][j] = sum[i-1][j] + sum[i-1][to[i-1][j]] + (ll)(to[i-1][j]-to[i][j])*(1<<(i-1));
q=read(); int l,r,x;
while(q--){
l=read(), r=read(), x=read();
ll a=calc(l,x)-calc(r+1,x), b=r-l+1, g=gcd(a,b);
printf("%lld/%lld
",a/g,b/g);
}
return 0;
}