LOJ 6435.「PKUSC2018」星际穿越

为了方便，定义 $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);
	}
}