P5465 星际穿越

题目传送门

思路

由题意得，每次从 i 可以跳一步到最小的点就是 l[i] .

由于是双向的，因此只要满足 $l[j]<=i(j>i)$ 那么便可以从 $j$ 一步跳到 $i$ ，记满足条件的最大的 $j$ 为 $rmax$ .

那么定义：

$f_{i,0}$ 代表从 $i$ 开始走 $2^0$ 次可以到达的最小的点。

那么 $f_{i,j}$ 代表从 $i$ 开始走第 $2^j$ 次可以到达的最小的点。

$f_{i,0}=l[i]$ ，也就是从 $i$ 走 $0(2^0)$ 次所能到达的最小的点。

再走一步呢？

那就是 $f_{i,1}=min^n_{k=l_i}l_k$ .

为什么是从 $i$ 跳一步所能到的最左端的点到 $n$ 这个区间内寻找更小的左端点呢？

为什么不是到 $rmax$ 呢？

其实就是 $rmax$ ，但是 $rmax$ 的左端点已经是满足条件最大的了，再往右，也就是从 $rmax+1$ 到 $n$ 都不会满足条件，也就是说这些点连 $i$ 都一步跳不到，怎么可能一步跳到比 l[i] 还小的点呢？

为了方便，所以写到 $n$ ，这样就不用特意计算 $rmax$ 了。

所以递推我们得到:

$f_{i,j}=f_{f_{i,j-1},j-1}$

也就是说，从 $i$ 开始走第 $j$ 次可以到达的最小的点就是从 $i$ 开始走 $2^{j-1}$ 次可以到达的最小的点到所有点之间的这些点，从这些点再跳 $2^{j-1}$ 步所能到达的最小的点。

这就有 倍增 的意思了。

但是，但是：

连续向左跳可不一定比先向右再向左跳更优。

所以 $f_{i,0}=min(l[i],f_{i+1,0})$ ，其中$f_{n,0}$一定为$l[n]$。

这个需要倒着往前推，这样就可以都保证是最优解

对于从 $n$ 开始的第一步，它所能到达的最小的点只能是它的 $l$ 值，因为它没法向右了。

这样的话从 $i$ 右边的 $j$ 号点先跳到 $i$ 还是先跳到 $i+1$ ，下一步都是一样的，因为贪心的缘故，假如 $i+1$ 往后跳更优，也就是 $f_{i+1,0}$ 更小，那么 $i$ 的下一步将和 $i+1$ 的下一步一致（因为 $f_{i,0}$ 的时候有个取 min 操作）。

---

根据答案形式为求区间期望，考虑前缀和优化。

用 $sum_{i,j}$ 代表从 $i$ 到 $f_{i,j}\to{(i-1)}$ 这些点的最小步数之和，也就是从 $i$ 转移 $2^j$ 步后所到达的最小的点到 $i-1$ 这段区间内到 $i$ 的最小步数之和（步数=转移次数）

转移：

$sum_{i,0}=i-f_{i,0}$

因为只用跳一次，区间内点的个数即转移代价。

$sum_{i,j}=sum_{i,j-1}+sum_{f_{i,j-1},j-1}+2^{j-1}\times({f_{i,j-1}-f_{f_{i,j}}})$

因为分了两次来跳，其实就是点的个数再把需要跳两遍的点再加一遍

在跳的过程中记录一下需要累加的次数即可。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+7;
int l[N];
int f[N][22],sum[N][22];
int n,m;
void init()
{
    f[n][0]=l[n],sum[n][0]=n-l[n];//画下图即理解,
    for(int i=n-1;i>=2;i--)//从n-1开始处理
    {
        f[i][0]=min(f[i+1][0],l[i]);//跳一步
        sum[i][0]=i-f[i][0];
    }
    for(int i=1;i<22;i++)
        for(int j=(1<<i);j<=n;j++)
        {
            f[j][i]=f[f[j][i-1]][i-1];//递推式
            sum[j][i]=sum[j][i-1]+sum[f[j][i-1]][i-1]+(1<<(i-1))*(f[j][i-1]-f[j][i]);
        }
    return;
}
int dist(int x,int y)//目标点，当前位置
{
    if(x>=l[y]) return y-x;//特判一步就能走到的
    int sp=1,ans=y-l[y];//先跳一步
    y=l[y];
    for(int i=20;i>=0;i--)
    {
        if(f[y][i]>=x)//还没跳到
        {
            ans+=sp*(y-f[y][i])+sum[y][i];//前缀和，有些数会被加sp遍，sum存的仅为走一步之和
            sp+=(1<<i);//走的这些都得加上
            y=f[y][i];//跳过来
        }
    }
    //下一次跳跳过了就停止转移，那么可能是刚好这一步跳到了，也可能还差一点
    if(y>x)//差一点，补上（类似倍增求LCA）
    {
        ans+=(sp+1)*(y-x);
    }
    return ans;
}
int gcd(int a,int b)
{
    return b>0?gcd(b,a%b):a;//辗转相除求gcd
}

int main()
{
    cin>>n;
    for(int i=2;i<=n;i++)
    {
        scanf("%d",&l[i]);
    }
    init();
    cin>>m;
    while(m--)
    {
        int L,R,X;
        scanf("%d%d%d",&L,&R,&X);
        int d=dist(L,X)-dist(R+1,X); //X为起点，从起点到左端点-起点到右端点+1（其实就是前缀和）
        int g=gcd(d,R-L+1);
        printf("%d/%d\n",d/g,(R-L+1)/g);
    }
    return 0;
}

---