「PKUSC2018」星际穿越（倍增）

倍增好题啊！

我们我们预处理 (f[x][i]) 表示 (x) 点最左到达的端点，(sum[x][i]) 表示 (x) 点最左到达的端点时 (f[x][i]sim x) 的答案，然后倍增的时候记录一个 (tot) 转移即可

(Code Below:)

#include <bits/stdc++.h>
using namespace std;
const int maxn=300000+10;
const int inf=0x3f3f3f3f;
int n,q,L[maxn],f[maxn][20],sum[maxn][20];

inline int read(){
    register int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return (f==1)?x:-x;
}

int calc(int l,int x){
    if(L[x]<=l) return x-l;
    int ans=x-L[x],tot=1;x=L[x];
    for(int i=19;i>=0;i--)
        if(f[x][i]>l){
            ans+=sum[x][i]+(x-f[x][i])*tot;
            x=f[x][i];tot+=1<<i;
        }
    return ans+(x-l)*(tot+1);
}

int main()
{
    n=read();L[1]=1;
    for(int i=2;i<=n;i++) L[i]=read();
    f[n+1][0]=inf;
    for(int i=n;i>=1;i--) f[i][0]=min(f[i+1][0],L[i]),sum[i][0]=i-f[i][0];
    for(int j=1;j<20;j++)
        for(int i=1;i<=n;i++)
            if(f[i][j-1]){
                f[i][j]=f[f[i][j-1]][j-1];
                sum[i][j]=sum[i][j-1]+sum[f[i][j-1]][j-1]+((f[i][j-1]-f[i][j])<<(j-1));
            }
    q=read();
    int l,r,x,up,down,val;
    while(q--){
        l=read(),r=read(),x=read();
        up=calc(l,x)-calc(r+1,x);down=r-l+1;
        val=__gcd(up,down);up/=val;down/=val;
        printf("%d/%dn",up,down);
    }
    return 0;
}