Steven_Meng's Blog

传送门

为了方便，定义$a[i]=g[i]$。

首先做一次差分，将$\sum _{y=l} ^r dist(y,x)$变成$\sum _{y=l}^x dist(y,x) - \sum _{y=r+1}^x dist(y,x)$

问题转换为给定$l,r$，求$\sum_{i=l}^{r-1} dist(i,r)$

不要从最短路的方向考虑，而是考虑从从$x$点走$k$步能够到达的点是哪些

首先，考虑$k=1$，显然能够到达的点是$[a[x],x-1]$，并且，$k=1$是最少的可能步数，于是$x->[a[x],x-1]$的最短路已经钦定为$1$了，注意到只有这些点到$x$的步数是$1$，于是以后的任何点到$x$的最短路绝对不是$1$

考虑$k=2$，（敲黑板），我们巧妙地定义$m[i],p[i]$数组，表示$[i,n]$的点走一步能够走到的最左的点，显然$m[i]= \min\\{ a[j] \\},(j\in [i,n]),p[i]$代表这个$j$，之后你就会发现它非常有用。

注意到$m[i]$有一个特殊的性质，$\forall x \in [m[i],p[i]-1] $，都能通过道路$p[i]->x$到达（也是废话，但是最容易忽略）

我们接着证明$[m[a[x],a[x]-1]$的所有点都可以通过$2$条道路从$x$到达：

1.若$p[a[x]] \in [a[x],x-1]$

那么可以通过两条道路$x->p[a[x]] (\because p[a[x]] \in [a[x],x-1])$

$p[a[x]] -> \forall y \in [m[a[x],a[x]-1] (\because p[a[x]] >= a[x])$

到达。

如果这里没有明白请回去看一下刚才说的性质。

2.若$p[a[x]] \in [x+1,n]$，注意到我们说的性质，$\forall y \in [m[a[x]],p[a[x]]-1] $，都可以通过一条道路$p[a[x]->y$到达，$\because x<p[a[x]] \therefore$ 存在$x->p[a[x]]$的道路。于是我们直接从$x->p[a[x]]$，再$p[a[x]]-> \forall y \in [m[a[x],a[x]-1]$即可通过两次到达。

3.若$p[a[x]] = x$ ，显然这样是不行的，因为$a[x] > m[a[i]]$。

考虑$k=3$，记$m[a[x]]=x_1$，所以有$[m[x_1],x_1-1]$的点可以通过$3$次到达。

考虑$k=4$，记$m[a[x_1]]=x_2$，所以有$[m[x_2],x_2-1]$的点可以通过$4$次到达。

……………………

最终这个最短路序列被分成$[a[x],x-1],[m[a[x]],a[x]-1],[m[m[a[x]]],m[a[x]]-1] , \cdots , [1, ...] $等部分，他们对答案的贡献分别是$1,2,3,4,\cdots$

不妨考虑换一种方法记录这个答案，这个答案等价于$x-1+(a[x]-1)+(m[a[x]]-1)+(m[m[a[x]]]-1)+(m[m[m[a[x]]]]-1) \cdots $

发现了什么，$m[m[]]$嵌套的格式让我们想起了倍增，于是我们记录$to[i][j]$，代表$m[m[m[...m[j]...]]$的值，其中嵌套了$2^i$个$m[]$

同样，也要记录$sum[i][j]$，代表上面那个东西的前缀和。

到了最终的问题，如何算出$\sum_{i=l}^{r-1} dist(i,r)$，考虑到我们在上面的计算过程中重复算了很多值，我们现在要一个一个减去，记$\min\\{ k,使得m[m[m[..(k个m)..m[x]]]] \le l \\}$，只有嵌套$\le k$次的$m[m[ ]]$才会对答案造成贡献，于是我们只要求出前$k$个即可。

而且注意到我们重复算了很多东西，对于$[1,l-1]$的数，每次都会被重复算，于是减去$k*(l-1)$即可。

这样就完了。

注意代码里面有一个小特判，如果$a[r]\le l$，那么每个数都可以通过一次调到$r$，答案就是$r-l$

#include <bits/stdc++.h>
#define MAXN 300005
#define LOG 25
using namespace std;
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while (ch<'0'||ch>'9'){
		if (ch=='-') f=-1;
		ch=getchar();
	}
	while (ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+(ch^'0');
		ch=getchar();
	}
	return x*f;
}
int a[MAXN],m[MAXN];
int to[MAXN][LOG],sum[MAXN][LOG];
inline int Calc(int l,int r){//sigma_{i=l}^r-1 dist(i,r)
	if (a[r]<=l) return (r-1)-l+1;
	int s=r-1,p=a[r],cnt=0;
	for (register int i=LOG-1;i>=0;--i){
		if (to[p][i]>l){//可以跳
			cnt|=(1<<i);
			s+=sum[p][i];
			p=to[p][i];
		}
	}
	s+=(p-1),cnt+=2;
	return s-cnt*(l-1);//去掉前面部分
}
int main(){
	int n=read();
	for (register int i=2;i<=n;++i) a[i]=read();
	m[n]=a[n];
	for (register int i=n-1;i>=1;--i){
		m[i]=min(m[i+1],a[i]);
	}
	for (register int i=1;i<=n;++i) to[i][0]=m[i],sum[i][0]=i-1;
	for (register int j=1;j<LOG;++j){
		for (register int i=1;i<=n;++i){
			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 q=read();
	while (q--){
		int l=read(),r=read(),x=read();
		int ans=Calc(l,x)-Calc(r+1,x);
		int down=r-l+1;
		int g=__gcd(ans,down);
		printf("%d/%d\n",ans/g,down/g);
	}
}