洛谷P5465 [PKUSC2018] 星际穿越题解

题目链接：P5465 [PKUSC2018] 星际穿越

题意：

有 \(n\) 个星球，它们的编号是 \(1\) 到 \(n\)，它们坐落在同一个星系内，这个星系可以抽象为一条数轴，每个星球都是数轴上的一个点，特别地，编号为 \(i\) 的星球的坐标是 \(i\)。

一开始，由于科技上的原因，这 \(n\) 个星球的居民之间无法进行交流，因此他们也不知道彼此的存在。现在，这些星球独立发展出了星际穿越与星际交流的工具。对于第 \(i\) 个星球，他通过发射强力信号，成功地与编号在 \([l_i,i-1]\) 的所有星球取得了联系(编号为 \(1\) 的星球没有发出任何信号)，取得联系的两个星球会建立双向的传送门，对于建立了传送门的两个星球 \(u,v\)，\(u\) 上的居民可以花费 \(1\) 单位时间传送到 \(v\)，\(v\) 上的居民也可以花费 \(1\) 单位时间传送到 \(u\) ，我们用 \(\mathrm{dist}(x,y)\) 表示从编号为 \(x\) 的星球出发，通过一系列星球间的传送门，传送到编号为 \(y\) 的星球最少需要花费的时间。

现在有 \(q\) 个星际商人，第 \(i\) 个商人初始所在的位置是 \(x_i\), 他的目的地是 \([l_i,r_i]\) 中的其中一个星球，保证 \(l_i<r_i<x_i\) 。他会在这些星球中等概率挑选一个星球 \(y\) (每个星球都有一样的概率被选中作为目的地)，然后通过一系列星球的传送门，花费最少的时间到达星球 \(y\) 。商人想知道他花费的期望时间是多少？也就是计算 \(\frac{1}{r_i-l_i+1}{\sum_{y=l_i}^{r_i}{\mathrm{dist}(x_i,y)}}\) 。

输入格式：

第一行一个正整数 \(n\) ，表示星球的个数。

第二行 \(n-1\) 个正整数，第 \(i\) 个正整数为 \(l_{i+1}\) ，表示编号在 \([l_{i+1},i]\) 区间内所有星球已经与编号为 \(i+1\) 的星球取得了联系，并且可以通过花费 1 单位进行彼此的传输。保证 \(l_{i+1}\leq i\) 。

第三行一个正整数 \(q\) ，表示询问组数。

接下来 \(q\) 行，每行三个数字 \(l_i,r_i,x_i\) ，表示在 \([l_i,r_i]\) 这个区间中等概率选择一个星球 \(y\)，\(dist(x_i,y)\) 的期望。保证 \(l_i<r_i<x_i\) 。

输出格式：

对于每组询问，注意到答案必然是一个有理数，因此以 \(p/q\) 的格式输出这个有理数，要求 \(\gcd(p,q)=1\) 。

如果答案为整数 \(m\) ，输出 \(m/1\) 。

数据范围：

\(2 \le n,q\leq 3\times 10^5\)

如果设 \(S(i,j)\) 表示以 \(i\) 为起点，走到 \([j,i-1]\) 中每个节点的最小步数之和

那么询问 \((l,r,v)\) 的答案就是 \(\frac{1}{r - l + 1} (S(v, l) - S(v, r + 1))\) 。

显然跳一次能调到的最小点是 \(l_i\) ，那么跳两次就是 \[ l'_j=\min_{l_i \le j \le n}l_j \] 跳三次就是 \[ l_j^{(2)} = \min_{l_i \le j \le n}l_j' \] 这个东西是有传递性的。考虑倍增。

设 \(f(i,j)\) 表示以 \(i\) 为起点，跳 \(2^j\) 次能跳到最小的点是哪个，则 \[ \begin{aligned} f(i,0) &= \min_{i\le k \le n} l_k \\[6pt] f(i,j) &= \min_{f(i, j - 1)\le k \le n} l_k = f(f(i,j-1),\,j-1) & (j > 0) \end{aligned} \] 注意 \(f(i,0)\) 是从 \(i\) 到 \(n\) 转移的，和上面的 \(l_j'\) 这些定义不同。

接着设 \(g(i,j)\) 以 \(i\) 为起点，走到 \([f(i,j),i-1]\) 中每个节点的最小步数之和，则 \[ \begin{aligned} g(i,0) &= n - f(i,0) \\[6pt] g(i,j) &= g(i,j-1) + g(f(i,j-1),\,j-1) + 2^{j-1}(f(i,j-1)-f(i,j)) & (j > 0) \end{aligned} \] 第二行可以这么理解：

从 \(f(i,j-1)\) 这个中转点出发跳 \(2^{j-1}\) 次贡献的确是 \(g(f(i,j-1),\,j-1)\)

但因为我们是从 \(i\) 出发的，所以 \([f(i,j),f(i,j-1)-1]\) 的每个点需要 \(2^{j-1}\) 步从 \([f(i,j-1),i-1]\) 中跳过来

提示：

这里前一个区间和后一个区间大小不一定相等，但前一个区间的点一定是从后一个区间跳过来的。

事实上我们也不关心后一个区间，因为从 \(i\) 出发能一步跳到 \(l_i\) ，亦能一步跳到 \([l_i,i-1]\) 中的任何一个点。

时间复杂度 \(\mathcal{O}((n+q) \log n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(3e5 + 15))

int f[N][21], g[N][21], l[N];
int gcd(int a, int b) { return !b ? a : gcd(b, a % b); }
int solve(int x, int y)
{
    if(l[x] <= y) return x - y;
    int sum = x - l[x], cnt = 1; x = l[x];
    for(int i = 20; ~i; i--)
        if(f[x][i] >= y)
        {
            sum += cnt * (x - f[x][i]) + g[x][i];
            cnt += (1 << i); x = f[x][i];
        }
    if(x > y) sum += cnt * (x - y) + x - y;
    return sum;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n; cin >> n;
    for(int i = 2; i <= n; i++) cin >> l[i];
    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] + (1ll << (j - 1)) * (f[i][j - 1] - f[i][j]);
        }
    int qwq; cin >> qwq;
    for(int _l, r, v; qwq--; )
    {
        cin >> _l >> r >> v;
        const int x = solve(v, _l) - solve(v, r + 1);
        const int y = r - _l + 1, d = gcd(x, y);
        cout << x / d << '/' << y / d << '\n';
    }
    return 0;
}