自动搬运

查看原文

来自洛谷，原作者为

	Fading AFO

搬运于2025-08-24 22:11:03，当前版本为作者最后更新于2019-07-18 10:16:32，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

这是一道非常有趣的题。

可以先做$\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;
}