题解 P5465 【[PKUSC2018]星际穿越】

· · 题解

这是一道非常有趣的题。

可以先做\texttt{[SCOI2015]国旗计划}。

网络上很多题解都不清楚自己的写法为什么是对的，甚至连自己定义的数组是什么都不知道，非常误人子弟。他们都没想清楚。

所以我来发布一篇好了。

设\text{sum}_{i,j}表示从i到j\sim i的所有点的最小步数之和。

首先，我们发现如果求出\text{sum}_{i,j}，

那么答案就是\frac 1{r-l+1}(\text{sum}_{x,l}-\text{sum}_{x,r+1})

怎么求呢？我们考虑一些显然的性质：

性质1

从x出发，可以一步到达最远的点为l_x，而且可以到达[l_x,x-1]的所有点。

废话！

性质2

如果x可以k步到达点y，那么一定可以到达[y,x-1]。

好像也很废话吧...

我们考虑快速求\text{sum}_{l,x}

我们第一步从x开始跳，可以跳到哪里呢？

显然可以跳到最小的点为l_x。最大的呢？是x？naive!

注意到题目里的边是双向的！

所以，最大的点，应该是所以满足l_k\leq x(k>x)的k的最大值！

可能有点绕，不过多看几次就明白了。

感谢 @Fee_cle6418 的指正

然后我们第二次跳跃，可以到达最小的点是什么呢？

这里给出结论，是

\min_{i=l_x}^nl_i

你可能想问，为什么是n而不是k_{\max}???

事实上两者均可，但是前者表述起来方便。

因为，对于(k_{\max}+1)\sim n之间的所有点，其l_i对答案不可能造成贡献。因为它们的l值比x还大。

以此类推，设第a(a>1)次的可以到达最小的点为b，第a+1次跳跃可以到达最小的点就是

\min_{i=b}^nl_i

这样我们就可以用倍增优化了。

设f_{i,0}表示\min\limits_{k=i}^nl_k,f_{i,j}=\min\limits_{k=f_{i,j-1}}^nl_k,g_{i,j}表示i到f_{i,j}\sim (i-1)所有点的最小步数之和。

具体转移

f_{i,j}=f_{f_{i,j-1},j-1} g_{i,j}=g_{i,j-1}+g_{f_{i,j-1},j-1}+2^{j-1}(f_{i,j-1}-f_{i,j})

这个转移画画图就理解了。

具体求法实现看看代码吧，这里不方便叙述。

inline ll get(ll x,ll to){//表示x->(to~x-1)内所有点的答案。
    if (L[x]<=to) return x-to;//特判
    ll ans=x-L[x],tot=1;x=L[x];//第一跳跃比较特殊，上文有写到。
    //tot表示已经跳了多少步
    for (int i=20;i>=0;i--){
        if (f[x][i]>=to){//如果跳2^i次还无法到达
            ans+=tot*(x-f[x][i])+g[x][i];//先算上答案，而且这些点跳到起始点依旧需要跳tot步。
            tot+=(1<<i);x=f[x][i];
        }
    }
    if (x>to) ans+=tot*(x-to)+x-to;//最后没有跳满，算上残余答案。
    return ans;
}

完整代码：

#include<bits/stdc++.h>
#define ll long long
#define ljc 998244353
using namespace std;
#ifdef Fading
#define gc getchar
#endif
#ifndef Fading
inline char gc(){
    static char now[1<<16],*S,*T;
    if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;}
    return *S++;
}
#endif
inline ll read(){
    register ll x=0,f=1;char ch=gc();
    while (!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
    while (isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=gc();}
    return (f==1)?x:-x;
}
int f[302001][21],g[302001][21],L[302001],n,Q;
inline ll get(ll x,ll to){
    if (L[x]<=to) return x-to;
    ll ans=x-L[x],tot=1;x=L[x];
    for (int i=20;i>=0;i--){
        if (f[x][i]>=to){
            ans+=tot*(x-f[x][i])+g[x][i];
            tot+=(1<<i);x=f[x][i];
        }
    }
    if (x>to) ans+=tot*(x-to)+x-to;
    return ans;
}
signed main(){
    n=read();
    for (int i=2;i<=n;i++){
        L[i]=read();
    }
    f[n][0]=L[n];g[n][0]=n-L[n];
    for (int i=n-1;i>=2;i--){
        f[i][0]=min(f[i+1][0],L[i]);
        g[i][0]=i-f[i][0];
    }
    for (int j=1;j<=20;j++){
        for (int i=(1<<j);i<=n;i++){
            f[i][j]=f[f[i][j-1]][j-1];
            g[i][j]=g[i][j-1]+g[f[i][j-1]][j-1]+(1<<j-1)*(f[i][j-1]-f[i][j]);
        }
    }
    Q=read();
    while (Q--){
        int l=read(),r=read(),X=read();
        ll fz=get(X,l)-get(X,r+1),fm=(r-l+1),G=__gcd(fz,fm);
        fz/=G;fm/=G;
        printf("%lld/%lld\n",fz,fm);
    }
    return 0;
}