题面
题解
我们先想想，在这个很特殊的图里该怎么走最短路
先设几个量，(a_i)表示([a_i,i-1])之间的点都和(i)有边（即题中的(l_i)），(l)表示当前在计算从(i)到([l,i])中的所有点的步数总和。那么答案就是([l,i]-[r+1,i])
因为(a_i)表示([a_i,i-1])之间的点都和(i)有边，那么如果从(i)出发，对于所有这个区间中的点，肯定是直接一步跳过去最优。证明显然
记(mn_i)表示(i)以及它右边所有的点中能跳到的最左边的点，对于所有([mn_{a_i},a_i-1])中的点，肯定能够两步跳到
证明：如果(mn_{a_i})是由([a_i,i-1])中的点跳到的，那么第一步从(i)跳到那个点，第二步跳过去。如果是由(i)右边的点跳到的，那么从(i)第一步跳到右边那个点，再跳过去即可
同理，记(x=mn_{a_i})，所有([mn_x,x-1])之间的点都能(3)步跳到，(y=mn_x)，则([mn_y,y-1])之间的点都能(4)步跳到……
我们把询问变成从(i)向左的两个区间相减的形式。那么从(i)出发，我们可以把左边的点分为若干段，每一段都有相同的最短步数
然而有可能(a_i=i-1)，即每一次都只能往左跳一步，上面的方法就(gg)了
让我们看看我们上面是怎么数总步数的……([a_i,i-1])乘个(1)，([mn_{a_i},a_i-1])乘个(2)，([mn_x,x-1])乘个(3)……
我们似乎可以换一个数法，先加上([1,i-1])，再加上([1,a_i-1])，再加上([1,x-1])……
那么这样数出来的答案只要记录一下一共数了(t)次，最后减去(t imes (l-1))就是正确答案了！
所以你这转化好像没啥子用啊……跳的次数还是没变啊……
然而我们可以倍增啊！记录一个倍增数组表示跳(i)步之后会到哪里，以及跳的这几步里的(i-1)的总和
然后就没有然后了
//minamoto
#include<bits/stdc++.h>
#define R register
#define ll long long
#define fp(i,a,b) for(R int i=a,I=b+1;i<I;++i)
#define fd(i,a,b) for(R int i=a,I=b-1;i>I;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
using namespace std;
char buf[1<<21],*p1=buf,*p2=buf;
inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
int read(){
R int res,f=1;R char ch;
while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);
for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');
return res*f;
}
char sr[1<<21],z[20];int K=-1,Z=0;
inline void Ot(){fwrite(sr,1,K+1,stdout),K=-1;}
void print(R ll x){
if(K>1<<20)Ot();if(x<0)sr[++K]='-',x=-x;
while(z[++Z]=x%10+48,x/=10);
while(sr[++K]=z[Z],--Z);sr[++K]='
';
}
const int N=3e5+5,L=21;
inline ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
int to[N][L],mn[N],a[N],st[N];ll sum[N][L];
int n,top,l,r,x,m;ll p,q,d;
ll calc(int x,int y){
ll res=0;int las=0,now,t=0;
if(y>=a[x])return x-y;
las=a[x],res=x-1;
fd(j,19,0)if(to[las][j]>y)t|=(1<<j),res+=sum[las][j],las=to[las][j];
t+=2,res+=las-1,res-=1ll*(y-1)*t;
return res;
}
void init(){
fp(i,1,n)to[i][0]=mn[i],sum[i][0]=i-1;
for(R int j=1;j<=19;++j)fp(i,1,n){
to[i][j]=to[to[i][j-1]][j-1];
sum[i][j]=sum[i][j-1]+sum[to[i][j-1]][j-1];
}
}
int main(){
// freopen("testdata.in","r",stdin);
n=read();
fp(i,2,n)mn[i]=a[i]=read();
fd(i,n-1,1)cmin(mn[i],mn[i+1]);
init();
m=read();
while(m--){
l=read(),r=read(),x=read();
p=calc(x,l)-calc(x,r+1);
q=r-l+1;
d=gcd(p,q),p/=d,q/=d;
print(p),sr[K]='/',print(q);
}
return Ot(),0;
}