「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/%d\n",up,down);

	}

	return 0;

}

巴特西

「PKUSC2018」星际穿越（倍增）

最新文章

热门文章