传送门
题意简述：
给一个序列，对于第iii个位置，它跟[limi,i−1][lim_i,i-1][limi,i−1]这些位置都存在一条长度为111的无向边。
称dist(u,v)dist(u,v)dist(u,v)表示(u,v)(u,v)(u,v)间最短路长度。
qqq次询问，每次给出l,r,xl,r,xl,r,x，求∑i=lrdist(i,x)\sum_{i=l}^rdist(i,x)∑i=lrdist(i,x)
思路：
有一个显然的结论，从iii走到它之前的点，要么向右边走一次之后一直向左走，要么一直向左走。
对每个点dpdpdp出它最多向右边走一次然后向左走一步能够到达的最小编号，称为mnimn_imni。
这样对于编号在[limi,i−1][lim_i,i-1][limi,i−1]间的点只用直接走一次，对于编号在[1,limi−1][1,lim_i-1][1,limi−1]的点可以先走到mnimn_imni，然后走到iii，这样用主席树维护[1,i−1][1,i-1][1,i−1]到iii的最短距离，iii对应的线段树用mnimn_imni的更新过来即可。
提示：bzoj轻微卡主席树，最好用fread优化
代码：
#include<bits/stdc++.h>
#define ri register int
using namespace std;
const int rlen=1<<18|1;
inline char gc(){
static char buf[rlen],*ib,*ob;
(ib==ob)&&(ob=(ib=buf)+fread(buf,1,rlen,stdin));
return ib==ob?-1:*ib++;
}
inline int read(){
int ans=0;
char ch=gc();
while(!isdigit(ch))ch=gc();
while(isdigit(ch))ans=((ans<<2)+ans<<1)+(ch^48),ch=gc();
return ans;
}
const int N=3e5+5;
int rt[N],lim[N],n,mn[N];
inline int gcd(int a,int b){while(b){int t=a;a=b,b=t-t/a*a;}return a;}
namespace SGT{
#define lc (son[p][0])
#define rc (son[p][1])
#define mid (l+r>>1)
int sum[N*30],add[N*30],son[N*30][2],tot=0;
inline void update(int&p,int l,int r,int ql,int qr){
int o=++tot;
sum[o]=sum[p],add[o]=add[p],son[o][0]=lc,son[o][1]=rc;
p=o;
if(ql<=l&&r<=qr){++add[p];return;}
sum[p]+=min(qr,r)-max(ql,l)+1;
if(qr<=mid)update(lc,l,mid,ql,qr);
else if(ql>mid)update(rc,mid+1,r,ql,qr);
else update(lc,l,mid,ql,mid),update(rc,mid+1,r,mid+1,qr);
}
inline int query(int p,int l,int r,int ql,int qr){
if(!p)return 0;
int ret=add[p]*(min(qr,r)-max(ql,l)+1);
if(ql<=l&&r<=qr)return sum[p]+ret;
if(qr<=mid)return query(lc,l,mid,ql,qr)+ret;
if(ql>mid)return query(rc,mid+1,r,ql,qr)+ret;
return query(lc,l,mid,ql,mid)+query(rc,mid+1,r,mid+1,qr)+ret;
}
#undef lc
#undef rc
#undef mid
}
int main(){
n=read();
for(ri i=2;i<=n;++i)lim[i]=mn[i]=read();
for(ri i=n-1;i;--i)mn[i]=min(mn[i+1],mn[i]);
for(ri i=2;i<=n;++i)rt[i]=rt[mn[i]],SGT::update(rt[i],1,n,1,i-1);
for(ri tt=read(),ans,len,g,l,r,x;tt;--tt){
l=read(),r=read(),x=read();
ans=len=r-l+1;
if(l<lim[x])ans+=SGT::query(rt[lim[x]],1,n,l,min(lim[x]-1,r));
g=gcd(ans,len);
cout<<ans/g<<'/'<<len/g<<'\n';
}
return 0;
}