「PKUSC2018」星际穿越

发表于 分类于

题目链接：https://loj.ac/problem/6435。

考虑从$x$出发，显然第一步可以走到$[l_x,x)$。

考虑第二步可以走到哪里，设$d_i=\min _{j=i}^{n} l_j$，那么稍微想下就可以知道第二步可以走到$[d_{l_x},l_x)$。

以此类推，假设第$i$步最远可以走到$p$，那么$i+1$步可以走到$[d_p,p)$。

那么对这个数组倍增就好了，复杂度$O(n\log n)$。

具体可以维护一个$g_{i,j}$表示$i\to [f_{i,j},i)$的最短路之和，$f_{i,j}$是倍增数组。

边界判一判就好了。

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
#include<bits/stdc++.h>
using namespace std;

#define int long long 

void read(int &x) {
    x=0;int f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}

void print(int x) {
    if(x<0) putchar('-'),x=-x;
    if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}

#define lf double
#define ll long long 

#define pii pair<int,int >
#define vec vector<int >

#define pb push_back
#define mp make_pair
#define fr first
#define sc second

#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++)

const int maxn = 1e6+10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 1e9+7;

int n,a[maxn],f[maxn][20],g[maxn][20];

int calc(int x,int l) {
    if(a[x]<=l) return x-l;
    int w=1,res=x-a[x];x=max(l,a[x]);
    for(int i=19;~i;i--) {
        if(f[x][i]<l) continue;
        res+=w*(x-f[x][i])+g[x][i];
        w+=1<<i,x=f[x][i];
    }if(x!=l) res+=(w+1)*(x-l);
    return res;
}

signed main() {
    read(n);
    for(int i=2;i<=n;i++) read(a[i]),f[i][0]=a[i];
    f[1][0]=1;
    for(int i=n-1;i;i--) f[i][0]=min(f[i][0],f[i+1][0]),g[i][0]=i-f[i][0];
    g[n][0]=n-f[n][0];
    for(int i=1;i<=n;i++)
        for(int j=1;j<20;j++) {
            f[i][j]=f[f[i][j-1]][j-1];
            g[i][j]=g[i][j-1]+g[f[i][j-1]][j-1]+(1ll<<(j-1))*(f[i][j-1]-f[i][j]);
        }
    int q;read(q);
    while(q--) {
        int x,l,r;read(l),read(r),read(x);
        int a=calc(x,l)-calc(x,r+1),b=r-l+1,g=__gcd(a,b);
        printf("%lld/%lld\n",a/g,b/g);
    }
    return 0;
}