题目：https://loj.ac/problem/6435
题解：https://www.cnblogs.com/HocRiser/p/9166459.html
自己要怎样才能想到怎么做呢……
dp[ t ][ i ] 表示从 [ i , n ] 这些点出发，走 2 步最左能走到哪。
sm[ t ][ i ] 表示从 [ i , n ] 出发，走到 [ dp[ t ][ i ] , i-1 ] 的最小步数和；比如一个终点 x 贡献的就是 [ i , n ] 里离 x 最近的那个点到 x 的距离。
sm[ t ][ i ] = sm[ t-1 ][ i ] + sm[ t-1 ][ dp[ t-1 ][ i ] ] + ( dp[ t-1 ][ i ] - dp[ t ][ i ] ) * 2
后面那个乘 2 的部分是这样考虑：
新扩展出来的部分是 [ dp[ t ][ i ] , dp[ t-1 ][ i ] ] 这部分。考虑从 [ i , n ] 走到其中一点 x 的长度，一定是 2 再加上一个到 x 具体的步数。
走 2 步之后的步数总和，一定恰好就是 sm[ t-1 ][ dp[ t-1 ][ i ] ] ；
不存在一个在 [ dp[ t ][ i ] , dp[ t-1 ][ i ] ] 里的点 x ，满足 sm[ t-1 ][ dp[ t-1 ][ i ] ] 里包含的步数已经包括了一些 “前 2 步” 的部分。因为如果除去包含在 sm[ t-1 ][ dp[ t-1 ][ i ] ] 里的部分之后，剩余的部分不足 2 步，那么 dp[ t-1 ][ i ] 还可以更多地扩展。
回答询问也可以类似地考虑。把询问 ( [ l , r ] , x ) 拆成 ( [ l , x-1 ] , x ) 和 ( [ r+1 , x-1 ] , x ) ，考虑从 x 开始往左尝试倍增。先走 2 步走到一个位置 k （k >= l） ，然后可以把 x 移动到 k 那个位置接着尝试倍增；不过这次操作之后的所有路径都要先走 2 步了，所以此时给答案贡献的是 sm[ t ][ x ] + ( dp[ t ][ x ] - l ) * 2 。
但是要特别考虑有没有先向右走了一步。
可以先向左走一步，设从 x 走到 x'，可以认为之后是可以 “从 [ x' , n ] 出发 ” 而不是 “ 从 x 点出发 ”了。
因为如果接下来继续向左走，合法。如果接下来从 [ x'+1 , n ] 的一个点开始走，那么相当于刚才 “向左走” 的一步其实是向右走或者走到了 [ x'+1 , x ] 的一个点上。
如果是相当于向右走的话，目标点一定是一步可以走到的。因为在最优决策里，下一步是要走到比 x 再往左的一个点，所以目标点一定也能从 x 一步走到。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
int rdn()
{
int ret=;bool fx=;char ch=getchar();
while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}
while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();
return fx?ret:-ret;
}
int Mn(int a,int b){return a<b?a:b;}
const int N=3e5+,K=;
int n,c[N],bin[K],lm,dp[K][N];
ll sm[K][N];
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll cal(int l,int r)
{
if(l>=c[r])return r-l;
ll ret=r-l; r=c[r];//ret=r-l for all based 1
for(int t=;t>=;t--)
if(dp[t][r]>=l)
{
ret+=sm[t][r]; r=dp[t][r];
ret+=(ll)(r-l)*bin[t];
}
if(r!=l)ret+=r-l;
return ret;
}
int main()
{
n=rdn();
for(int i=;i<=n;i++)c[i]=rdn();
bin[]=;for(lm=;bin[lm-]*<=n;lm++)bin[lm]=bin[lm-]*;
lm--; dp[][n+]=n+;
for(int i=n;i;i--)
{
dp[][i]=Mn(dp[][i+],c[i]);//dp[0][1]=0
sm[][i]=i-dp[][i];
}
for(int t=;t<=lm;t++)
for(int i=;i<=n;i++)
{
if(!dp[t-][i])continue;
dp[t][i]=dp[t-][dp[t-][i]];
sm[t][i]=sm[t-][i]+sm[t-][dp[t-][i]]+
(ll)(dp[t-][i]-dp[t][i])*bin[t-];
}
int Q=rdn(),l,r,x;
while(Q--)
{
l=rdn();r=rdn();x=rdn();
ll a=cal(l,x)-cal(r+,x),b=r-l+;
ll g=gcd(a,b);
printf("%lld/%lld\n",a/g,b/g);
}
return ;
}
还有主席树做法。感觉有些难理解……并且（对自己来说）很难想到。
题解：https://www.cnblogs.com/skylee03/p/9160594.html
https://blog.csdn.net/lvzelong2014/article/details/83211203
https://blog.csdn.net/As_A_Kid/article/details/80726327?utm_source=blogxgwz8
https://www.cnblogs.com/Khada-Jhin/p/9629188.html
想了半天它是什么意思、正确性之类的。下面用 c[ i ] 表示题面里的 l[ i ] 。
流程：1.每个点 i 找一个 mn[i] ，表示 [ i , n ] 里面最小的 c[ i ] （注意是 [ i , n ] 不是 [ i+1 , n ]）；
2.每个点 i 开一个线段树维护 ” [ i-1 , n ] 的每个点到 i 的距离 “ ； 认为 ” 到 i 的距离 “ = ” 到 mn[ i ] 的距离+1 “ ，如果是在 [ mn[ i ] + 1 , i-1 ] 的点，认为到 i 的距离是 1 ；
所以 i 号点的线段树与 mn[ i ] 的线段树的不同就是 [ 1 , i-1 ] 的值 + 1 ；用主席树实现；
3.查询的时候， [ c[ i ] , i-1 ] 与询问区间 [ l , r ] 相交的部分的答案是 1 ；
4.剩余部分的答案就在线段树上查，认为到 i 的距离就是线段树上存的到 c[ i ] 的距离 + 1 ；
线段树里存的 ” 每个点到 i 的距离 “ 其实指的是 ”迂回“ 到 i 的距离；
比如 x 到 i 的路径就是 x 走到 ” c[ k ] = mn[ i ] 的那个点 k “ ，然后再走到 i ；线段树上的值没有计算最后 ”拐回去走到 i “ 的那一步。
像上述一样做出主席树，可以使得求出的 ”每个点迂回到 i 的步数“ 最小；正确性不是很清楚……
对于这步的过程的一个理解，可以考虑一个点 x ，在 mn[ i ] 的线段树上存了 x ”迂回“ 到 i 的距离；
因为发出 mn[ i ] 的点可以是 i 自己，所以这个 ”迂回“ 也包括 x 直接跳到了 i 点；
线段树上，从 mn[ i ] +1 就变成到 i 的距离，考虑 x 可以 ”迂回“ 到 mn[ i ] ，那么计入步数的最后一步一定是走到了 >=mn[ i ] 的一个点（那个点是发出 mn[ mn[i] ] 的那个点）；
从那个点可以一步走到发出 mn[ i ] 的点的（因为该点 >=mn[ i ] ，所以可以走到发出 mn[ i ] 的点）。
查询的时候，在 [ c[ i ] , i-1 ] 之外的询问点，是用了线段树上存的到 c[ i ] 的值，然后 +1 作为到 i 的距离；
表示一个询问点 x ，先 ”迂回“ 地走到 c[ i ] ，但没有走最后一步，而是把最后一步改成走到 i 号点；
这是可以做到的，因为是 ”迂回“ ，所以走最后一步之前一定走到了 >= c[ i ] 的点；如果是 <= i-1 的，那么可以直接走到 i ；如果是 > i 的，因为可以跳到 c[ i ] ，所以可以一步跳到 i ；
这个最后一步不可能正好已经跳到了 i 点，因为 ”迂回到 i “ 是借道发出 mn[ i ] 的那个点的；如果倒数第二步跳到 i 点，说明 mn[ c[ i ] ] = c[ i ] ，但 mn[ i ] < i ，因为 mn[ i ] 对 c[ i ] 取了 min 。
但不太明白这为什么是最优的……
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
#define ls Ls[cr]
#define rs Rs[cr]
using namespace std;
int rdn()
{
int ret=;bool fx=;char ch=getchar();
while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}
while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();
return fx?ret:-ret;
}
int Mn(int a,int b){return a<b?a:b;}
int Mx(int a,int b){return a>b?a:b;}
const int N=3e5+,M=*N;
int n,c[N],pr[N];
int rt[N],tot,Ls[M],Rs[M],tg[M]; ll sm[M];
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
int nwnd(int pr)
{
int cr=++tot; ls=Ls[pr]; rs=Rs[pr];
tg[cr]=tg[pr]; sm[cr]=sm[pr];
return cr;
}
void mdfy(int l,int r,int &cr,int pr,int L,int R)
{
cr=nwnd(pr);
sm[cr]+=Mn(r,R)-Mx(l,L)+;//
if(l>=L&&r<=R){ tg[cr]++;return;}
int mid=l+r>>;
if(L<=mid)mdfy(l,mid,ls,Ls[pr],L,R);
if(mid<R)mdfy(mid+,r,rs,Rs[pr],L,R);
}
ll qry(int l,int r,int cr,int L,int R)
{
if(!cr)return ;//
if(l>=L&&r<=R)return sm[cr];
ll ret=(Mn(r,R)-Mx(l,L)+)*tg[cr];
int mid=l+r>>;
if(L<=mid)ret+=qry(l,mid,ls,L,R);
if(mid<R)ret+=qry(mid+,r,rs,L,R);
return ret;
}
int main()
{
n=rdn();
for(int i=;i<=n;i++)c[i]=rdn();
pr[n]=c[n];
for(int i=n-;i;i--)
pr[i]=Mn(pr[i+],c[i]);
for(int i=;i<=n;i++)
mdfy(,n,rt[i],rt[pr[i]],,i-);
int Q=rdn(),l,r,x;
while(Q--)
{
l=rdn();r=rdn();x=rdn();
ll a=r-l+,b=a; r=Mn(r,c[x]-);
if(l<=r)
{
ll d=qry(,n,rt[c[x]],l,r);
//c[x]!!! not pr[x] / x!!!
a+=d;
}
ll g=gcd(a,b);
printf("%lld/%lld\n",a/g,b/g);
}
return ;
}