洛谷p5465 [PKUSC2018]星际穿越【洛谷p5465】【PKUSC2018】星际穿越

【洛谷p5465】【PKUSC2018】星际穿越

题面

洛谷

题解

众所周知PKUSC的题大多都不可做，今天好不容易看到1个倍增水题（我猜当时应该全场切了）。
我们设(f[i][j])表示(i)点走(j)步可以到达的最左的点。
于是(f[i][j + 1] = min^{i-1}_{k=f[i][j]}l[k])
我们发现这个东西是可以倍增优化的。
于是就做完了...

代码

#include <bits/stdc++.h>

using std::min;  
using std::abs;   
const int maxn = 3e5 + 10;  
typedef long long ll;

template<class t> inline void read(t& res) {
    res = 0;  char ch = getchar();  bool neg = 0;
    while(!isdigit(ch))
        neg |= ch == '-', ch = getchar();
    while(isdigit(ch))
        res = (res << 1) + (res << 3) + (ch & 15), ch = getchar();
    if(neg)
        res = -res;
}

int n, m, i, j, k, q;   
int l[maxn], f[maxn][20], g[maxn][20];   

int gcd(int a,int b) { return b ? gcd(b,a % b) : a; }
inline int calc(int cl,int x) {
    if(cl >= l[x])
        return x - cl;
    int res = x - cl, j = 0;  x = l[x];
    for(int i = 19;~i;i--) {
        if(f[x][i] >= cl) {
            res += g[x][i] + (x - f[x][i]) * j;
            j += 1 << i;
            x = f[x][i];  
        }       
    }
    res += (x - cl) * (j + 1);
    return res;
}

int main() {
    read(n);
    l[1] = 0;
    for(int i = 2;i <= n;i++)
        read(l[i]);
    f[n][0] = l[n];
    for(int i = n - 1;~i;i--)
        f[i][0] = min(f[i + 1][0],l[i]), g[i][0] = i - f[i][0];
    for(int j = 1;j <= 19;j++)
        for(int i = 1;i <= n;i++)
            if(f[i][j - 1])
                f[i][j] = f[ f[i][j - 1] ][j - 1];
    for(int j = 1;j <= 19;j++)
        for(int i = 1;i <= n;i++)
            if(f[i][j])
                g[i][j] = g[i][j - 1] + g[ f[i][j - 1] ][j - 1] + (f[i][j - 1] - f[i][j]) * (1 << j - 1);  
    read(q);
    while(q--) {
        int L, R, x;  read(L);  read(R);  read(x);
        int a = calc(L,x) - calc(R + 1,x), b = R - L + 1, c = gcd(a,b);      
        printf("%d/%dn",a / c,b / c);      
    }   
    return 0;
}