题意
给定 $n$ 个点, 每个点与 $[l_i,i-1]$ 之间的点建立有单位距离的双向边. $q$ 组询问从 $x$ 走到 $[l,r]$ 中的随机一点的期望距离. 输出既约分数.
$n,q\le 3\times 10^5$, $l<r<x$.
题解
显然对于一个 $k$, $k$ 步之内能到达的点是 $[1,x)$ 的一个后缀. 那么也就是说 $[1,x)$ 中的点的答案被分成了若干段, 每段的答案相同且向前递增.
手动模拟一下, 我们发现第一步可以走到的左端点是 $l_x$, 第二步可以走到的就是 $\min\limits_{k\ge l_x}l_k$ 了. 原因是所有可能一步到达 $\min\limits_{k\ge l_x}l_k$ 的点都必然可以被 $x$ 一步到达(如果 $l_k$ 在 $k>x$ 处取得最小值, 那么显然 $l_k<x$. 又由于 $k$ 连接的是 $[l_k,k)$, 那么必然和 $x$ 直接相连). 且后面的步骤都是形如 $l_k$ 的后缀 $\min$ 的形式.
于是我们可以在第二步及以后尝试倍增.
倍增的同时不仅记录到达的左端点, 同时记录一下倍增时跳过的点的距离总和. 这样就可以在 $O(\log n)$ 的时间内计算出 $x$ 到 $[l,x)$ 内的所有点的最短路之和了. 两个后缀和相减即可得到 $[l,r]$ 内的答案.
最后约分一下输出就完了. 虽然最终答案是 $O(n^2)$ 级别的但是数据比较弱并没有爆 int…
参考代码
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
|
#include <bits/stdc++.h>
const int MAXN=3e5+10;
int n;
int q;
int l[MAXN];
int lg[MAXN];
int sum[20][MAXN];
int prev[20][MAXN];
int* minl=prev[0];
int ReadInt();
int Calc(int,int);
int main(){
n=ReadInt();
for(int i=2;i<=n;i++)
l[i]=ReadInt();
q=ReadInt();
l[1]=1;
minl[n+1]=n;
for(int i=n;i>=1;i--){
minl[i]=std::min(l[i],minl[i+1]);
sum[0][i]=i-minl[i];
}
for(int i=1;i<=n;i++)
sum[0][i]=i-minl[i];
for(int i=1;(1<<i)<=n;i++){
lg[1<<i]=1;
for(int j=1;j<=n;j++){
prev[i][j]=prev[i-1][prev[i-1][j]];
sum[i][j]=sum[i-1][j]+sum[i-1][prev[i-1][j]]+((prev[i-1][j]-prev[i][j])<<(i-1));
}
}
for(int i=1;i<=n;i++)
lg[i]+=lg[i-1];
for(int i=0;i<q;i++){
int l=ReadInt(),r=ReadInt(),pos=ReadInt();
int a=Calc(pos,l)-Calc(pos,r+1);
int b=r-l+1;
int gcd=std::__gcd(a,b);
printf("%d/%d\n",a/gcd,b/gcd);
}
return 0;
}
int Calc(int pos,int lim){
if(l[pos]<lim)
return pos-lim;
int dis=0,p=l[pos],ans=pos-lim;
// printf("x %d %d\n",ans,p);
for(int i=lg[p];i>=0;i--){
if(lim<=prev[i][p]){
ans+=sum[i][p]+(p-prev[i][p])*dis;
// printf("$ %d Q(%d,%d) %d\n",i,pos,lim,ans);
p=prev[i][p];
dis|=(1<<i);
}
}
return ans+(p-lim)*(dis+1);
}
inline int ReadInt(){
int x=0;
register char ch=getchar();
while(!isdigit(ch))
ch=getchar();
while(isdigit(ch)){
x=x*10+ch-'0';
ch=getchar();
}
return x;
}
|
