【洛谷5465】[PKUSC2018] 星际穿越(倍增)

点此看题面

大致题意: 给定(l_{2sim n}),其中(l_i)表示([l_i,i-1])的所有点与(i)之间存在一条长度为(1)的双向路径。每次询问给出(l,r,x),求(frac 1{r-l+1}sum_{y=l}^{r}dist(x,y))

重要性质

首先我们需要知道,这道题关键在于如何求出任意两点间的距离。

一个简单的性质,从(i)出发,如果你能通过(t)步到达(x),则必然能到达满足(xle yle i)的任意(y)

而现在我们来考虑一个重要的问题,即:从点(i)出发,经过一步,能到达哪些点?

首先,([l_i,i-1])显然是能够到达的。

然后呢?再仔细去研究一下,便会发现题目中提到路径是双向的,所以对于那些(l_xle i)(x>i)(x),也是能够到达的。

那么,从点(i)出发,经过两步,能到达的编号最小的点是什么呢?

这自然就是所有(i)经过一步能到达的点所能一步到达的编号最小的点中编号最小的了,即:

[min_{k=l_i}^nl_k ]

注意,之所以这里枚举的范围可以是(l_isim n),是因为这一范围中除去符合条件(即能够一步到达)的点以外都是(l_x>i)的点,这些点自然无法对答案造成贡献,因此枚举在内并无影响。

继续下去,从点(i)出发,经过三步,能到达的编号最小的点是什么呢?

很显然,如果设经过(x)步能到达的编号最小的点为(p_x),那么:

[p_3=min_{k=p_2}^nl_k ]

推广可知:

[p_x=min_{k=p_{x-1}}^nl_k ]

然后我们就可以发现,除去第一步能到达的点比较特殊以外,其余时候能到达的点都有一定规律。

实际上,在已确定当前能到达的编号最小的点的情况下,下一步能到达的编号最小的点是唯一确定的。

于是乎,我们就能想到倍增。

倍增

首先我们特殊处理第一步,因为它比较特殊。

接下来,我们设(f_{x,y})表示(x)再走(2^y)步所能到达的编号最小的点,并用(g_{x,y})表示([f_{x,y},x-1])范围内所有点到(x)的距离之和。

(f)的预处理,显然就是传统的(f_{x,y}=f_{f_{x,y-1},y-1}),而(g)的预处理就要略显复杂。

首先,([f_{x,y-1},x-1])(x)的路径总和(g_{x,y-1})([f_{x,y},f_{x,y-1}-1])(f_{x,y-1})的路径总和(g_{f_{x,y-1},y-1})显然都是要计算在内的。

([f_{x,y},f_{x,y-1}-1])内的点从(f_{x,y-1})(x)的距离都要另行计算,而这一距离实际上就是(2^{y-1})

又因为要计算这一距离的点共有(f_{x,y-1}-f_{x,y})个,所以(g_{x,y}=g_{x,y-1}+g_{f_{x,y-1},y-1}+(f_{x,y-1}-f_{x,y}) imes 2^{y-1})

如果定义一个函数(Jump(x,y)),其值为([y,x-1])范围内所有点到(x)的距离之和,则有:

[sum_{y=l}^{r}dist(x,y)=Jump_(x,l)-Jump(x,r+1) ]

也就是说,实现(Jump(x,y))之后,我们就可以差分计算出答案了。

(Jump(x,y))的实现,就可以利用上面的倍增数组。

先特殊处理第一步,初始化答案为(x-l_x)(实际上就是(1 imes(x-l_x)))。然后更新(x)(l_x)(因为这一部分的答案已经计算过了),并初始化(k=1)(表示接下来所有点到初始(x)的距离都需要加上(1)),接下来从大到小枚举(i)表示前进(2^i)步。

对于([f_{x,i},x-1])到现在(x)的距离,就是(g_{x,i}),而其到初始(x)的距离还要加上(k),由于共有(x-f_{x,i})个点,因此也就是加上(k(x-f_{x,i}))。然后我们更新(x)(f_{x,i}),并将(k)加上(2^i)

重复此流程,即可。

注意最后还要求一次剩余点到(x)的距离,因为并不是所有点都恰好是(f)的,以保证处理完毕。

具体实现详见代码。

代码

#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 300000
#define LN 20
#define LL long long
using namespace std;
int n,a[N+5],f[N+5][LN+5];LL g[N+5][LN+5];
class FastIO
{
	private:
		#define FS 100000
		#define tc() (A==B&&(B=(A=FI)+fread(FI,1,FS,stdin),A==B)?EOF:*A++)
		#define pc(c) (C==E&&(clear(),0),*C++=c)
		#define tn (x<<3)+(x<<1)
		#define D isdigit(c=tc())
		int T;char c,*A,*B,*C,*E,FI[FS],FO[FS],S[FS];
	public:
		I FastIO() {A=B=FI,C=FO,E=FO+FS;}
		Tp I void read(Ty& x) {x=0;W(!D);W(x=tn+(c&15),D);}
		Tp I void write(Ty x) {W(S[++T]=x%10+48,x/=10);W(T) pc(S[T--]);}
		Tp I void write(Con Ty& x,Con char& y) {write(x),pc(y);}
		I void clear() {fwrite(FO,1,C-FO,stdout),C=FO;}
}F;
I LL Jump(RI x,CI y)//倍增求答案
{
	if(y>=a[x]) return x-y;LL t=x-a[x],k=1;x=a[x];//特殊处理第一步
	for(RI i=LN;~i;--i) y<=f[x][i]&&(t+=k*(x-f[x][i])+g[x][i],k+=1<<i,x=f[x][i]);//重复执行中间过程
	return t+=k*(x-y)+(x-y);//最后保证处理完毕
}
I LL gcd(Con LL& x,Con LL& y) {return y?gcd(y,x%y):x;}//求最大公约数,用于约分
int main()
{
	RI Qt,i,j,x,y,z;LL t,d;for(F.read(n),i=2;i<=n;++i) F.read(a[i]);//读入数据
	for(f[n][0]=a[n],g[n][0]=n-a[n],i=n-1;i;--i) f[i][0]=min(a[i],f[i+1][0]),g[i][0]=i-f[i][0];//初始化f和g
	for(j=1;j<=LN;++j) for(i=1;i<=n;++i) f[i][j]=f[f[i][j-1]][j-1],//倍增打表f
		g[i][j]=g[i][j-1]+g[f[i][j-1]][j-1]+((1LL*f[i][j-1]-f[i][j])<<j-1);//倍增打表g
	F.read(Qt);W(Qt--) F.read(x),F.read(y),F.read(z),//处理询问
		t=Jump(z,x)-Jump(z,y+1),d=gcd(t,y-x+1),F.write(t/d,'/'),F.write((y-x+1)/d,'
');//差分
	return F.clear(),0;
}
原文地址:https://www.cnblogs.com/chenxiaoran666/p/Luogu5465.html