Steven_Mengの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 xp[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$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#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);
}
}

 评论