题解：P5465 [PKUSC2018] 星际穿越

很多题解仅仅把这道题的倍增优化 DP 当成类似树上倍增 LCA 的简单倍增。

但实际上直观定义出来的 DP 状态在某些方面上没有最优子结构性质（下文会展开叙述），并不适合倍增，而是需要进行一些特殊转化才能用倍增优化，本题解用等效法来构造合适的 DP 状态。

题目分析

形式化题意

形式化的，给定一个数轴上的

n(n\le3\times10^5)

个点，编号

1, 2, 3, \dots, n

，对每个点

i

，给定

l_i(l_i<i)

，将其与

[l_i, i-1]

内的所有点连一条长度为

1

的无向边，规定

dist(x, y)

表示从

x

到

y

的最短路径长度。
接下来给出

q(q\le3\times10^5)

次询问，每次给出

l<r<x

，求

\frac{1}{r-l+1}\times\sum\limits_{i=l}^rdist(x, i)

，以最简分数形式输出。

注：下文为了区分与联系相关的 $l_i$ 和与询问相关的 $l_x$ ，所有与联系相关的 $l_i$ 均含有下标（例如 $l_*$ ），与询问相关的全部用单独的 $l$ 。

编码要求

显然，我们的主要任务对每次询问求出

\sum\limits_{i=l}^rdist(x, i)

，然后使用 std::__gcd 约分即可。

考虑到

n,q\le3\times10^5

，程序的复杂度应该是亚平方级的，例如

O(n\log n), O(n\sqrt n)

（似乎这题单次分块的复杂度是

O(n\sqrt n)

，但这题分块编码并不比倍增编码简单）。

暴力算法

容易想到 Floyd 多源最短路算法，复杂度

O(n^3)

，显然不能通过。

但这个算法的真正意义是写对拍，因为 Floyd 编码很简单且不易写错，而且这题构造数据，将输入转为邻接矩阵也很简单，这里不再赘述。

正解 DP

首先容易想到 DP，因为传送过程存在明显的无后效性，前面如何到达

i

与

i

之后的传送路径无关。

但是，如果我们直观定义

dp[i][j]

表示从

i

出发走

j

步能到达的最左端位置，会发现它并不符合最优子结构：

dp[i][j+1]

并不一定是最后通过

dp[i][j]

到达的。

例如样例中以 $6$ 为起点，走 $1$ 步能到达的最左端位置为 $4$ ，走 $2$ 步能到达的最左端位置为 $1$ ，然而这个位置 $1$ 是从位置 $5$ 而非位置 $4$ 走过来的。

这限制了我们用倍增法优化这个 DP 状态，我们需要找到其它有用的 DP 状态。

引理 1

\text{Lemma 1}

：将第 $i$ 个星球的联系区间由 $[l_i, i-1]$ 改为 $[l_i, n]$ ，询问的答案不变。
换句话说，我们可以认为从

i

出发可以一步到达的点为

[l_i, n]

内的所有点，而不改变答案。

证明

注：下面各子引理的证明比较废话，读者可自行画图理解。

显然

\text{Lemma 1}

只是增加了边而没有删除边，那么答案不会增大。

引理 1.1

\text{Lemma 1.1}

：如果最短路径存在向右的传送，那么所有向右的传送不在任何向左的传送之后。

证明：假设在某一步向右传送(

b\rightarrow c

)，在向左传送(

b\leftarrow a

)之后，有以下情况：

$c=a$ ：无需多言。
$c<a$ ：可得 $l_a\le b<c<a$ ，那么可以直接 $c\leftarrow a$ ，那么原路径就不是最短路径了。
$c>a$ ：可得 $l_c\le b<a<c$ ，同样可以 $a\rightarrow c$ ，原路径不是最短路径。

根据

\text{Lemma 1.1}

我们可以知道，最短路径要么一直向左传送，要么先向右传送再一直向左传送。

引理 1.2

\text{Lemma 1.2}

：最短路径不存在连续多次向右的传送。

证明：假设引理不成立，根据

\text{Lemma 1.1}

，必然在开始就向右传送到起始点

x

的右侧，由于终点在

x

的左侧，必然存在唯一的一步

a\xleftarrow{x}b

，满足

a<x\le b

。

若 $x=b$ ，无需多言。
若 $x<b$ ，则 $l_b\le a<x<b$ ，那么可以直接 $x\rightarrow b$ ，再 $a\leftarrow b$ 两步到达 $a$ ，而那些连续多次向右的路径，至少花了 $3$ 步才到达 $a$ 。

根据

\text{Lemma 1.1}, \text{Lemma 1.2}

，最短路径要么是一直向左传送，要么是先向右传送一次再一直向左传送。

引理 1.3

\text{Lemma 1.3}

：如果最短路径以向右的传送开始，那么存在一个第一步相同的最短路径，其下一步向左传送的终点 $a<l_x$ 。

证明：假设

a\ge l_x

，有以下情况：

$a=x$ ，无需多言。
$a<x$ ，有 $l_x\le a<x$ ，那么可以从 $x$ 出发传送到 $a$ ，无需向右传送。
$a>x$ $a > x$ ，对于存在的唯一一步 $b\xleftarrow{x}c$ $b x c$ ，满足 $b<x\le c$ $b < x \leq c$ ，有以下情况：
1. $x=c$ ，无需多言。
2. $x<c$ ，有 $l_c\le b<x<c$ ，那么可以直接 $x\rightarrow c$ , $b\leftarrow c$ 两步到达 $b$ ，而原路径至少花了两步才到达 $b$ 。

首先，在

\text{Lemma 1}

的条件下，

\text{Lemma 1.1}, \text{Lemma 1.2}, \text{Lemma 1.3}

依然成立。

由于新条件只扩大了向右传送的区间，而没有改变向左传送的区间，因此新规则下的严格更短路径一定存在向右的移动

x\rightarrow a

，并且

x\rightarrow a

原本不合法。

根据

\text{Lemma 1.3}

，存在一个至少同样长的严格更短路径，

x\rightarrow a

的下一步

b\leftarrow a

满足

b<l_x

，有

l_a\le b<l_x\le x<a

，那么

x\rightarrow a

是合法的，矛盾，因此不存在新规则下的严格更短路径，即答案不会减小，得证。

回归题目

接下来的讨论都在

\text{Lemma 1}

的状态下。

\text{Lemma 1.1}, \text{Lemma 1.2}

提到，仅有第一步可能是向右的，其它步都是向左的，为此我们可以特殊处理第一步：

显然一步能到达 $[l_x, n]$ 的所有节点，将其与询问区间 $[l, r]$ 取交集，得到从 $x$ 出发能一步到达的所有点，然后从询问 $[l, r]$ 中去掉这个交集，并将答案（这里的答案指 $\sum\limits_{i=l}^rdist(x, i)$ ，下同）加上区间长。

注意，可能有 $[l, r]\subset[l_x, n]$ ，那么询问区间内的所有点都可一步到达，正确更新答案后直接退出计算即可。

尽管我们只知道终点在

l_x

左侧，但是容易贪心地找到第一步的固定终点：那就是使

l_y

最小的

y\in[l_x, n]

，显然其它第一步终点可直达的点，对于

y

也是可直达的。注意这个

y

可能在

x

的左侧也可能在

x

的右侧，但一定不是

x

，因为

l_{l_x}<l_x

恒成立，因此不用担心出现"原地跳跃"的情况。

定义

s_i=\min\{l_y, i\le y\le n\}

，那么第一步的固定终点的

l_*

值等于

s_{l_x}

，贡献最小值的

y

并不重要。

将等效起点转移到

y

上，剩余的

[l, r]

上的点都要走一步

x\rightarrow y

，答案增加

r-l+1

，然后将起点转移到

y

上即可。

考虑第

j+1

步的起点，即第

j

步的终点，我们发现选择

j

步可达的所有点中

l_i

最小的点一定不劣，和上面选择第一步的终点是同一个道理。

但是这样还是太麻烦了，为什么不把那个最优点计入到

j

步可达的左端点上呢？换言之，尽管最左端点不是下一步的好"跳板"，但它可以"借用"右边的点做"跳板"。

引理 2

\text{Lemma 2}

：如果起点 $x$ 满足 $\nexists x'>x, l_x'<l_x$ ，那么将第 $i$ 个星球的联系区间由 $[l_i, n]$ 改为 $[s_i, n]$ ，询问的答案不变。

证明

注：证明还是比较废话，同样容易画图理解。

用归纳法证明，显然新条件的答案不会增大。
因此我们只需要证明新条件下

j

步可达的点，在原条件下可以至多

j

步到达即可。

当 $j=1$ 时，因为 $s_x=l_x$ ，否则与引理前提矛盾，引理显然成立。
当 $j>1$ 时， $j-1\ge1$ ，设 $j-1$ 步可达的最左端点为 $a$ （由归纳法两种条件下都是一样的），列出两种条件下计算得到的 $j$ 步可达最左端点：
- 原条件： $\min\{l_i, a\le i\le n\}$
- 新条件： $\min\{s_i, a\le i\le n\}$
  考虑 $s$ 的递推定义： $s_i=\min\{s_{i+1}, l_i\}, 1\le i<n$ ，上式等价于 $s_a=\min\{l_i, a\le i\le n\}$
形式上都一模一样，引理成立。

我们第一步完成后的等效起点其实就符合

\text{Lemma 2}

的前提。

DP 状态定义

在

\text{Lemma 2}

的状态下，定义

dp[i][j]

表示从

i

出发

j

步可达的最左端点。

由于允许使用右侧的节点代替做"跳板"，新的 DP 状态具有明显的最优子结构特性：

dp[i][j+1]

可以从

dp[i][j]

转移过来，转移方程如下：

dp[i][1] = s_i

dp[i][j+j']=dp[dp[i][j]][j'], j, j'>1

有了新的最优子结构特性，容易得到倍增优化的转移方程：

dp[i][2^0] = s_i

dp[i][2^{j+1}]=dp[dp[i][2^j]][2^j]

求解答案

首先按照前面的方法特殊处理第一步，然后跳到新的等效起点，这个等效起点符合

\text{Lemma 2}

的前提，可以使用

dp

加速跳跃。

接下来用倍增跳跃用最少步数

j

到达

r

，方法和树上倍增求 LCA 的第二阶段类似，如果从当前点

i

出发走

2^j

不能到达目标，则走

2^j

步，并移动到

dp[i][2^j]

上。
这里仍然使用等效起点的思路，将起点转移到

dp[i][2^j]

上，然后答案增加

2^j\times(r-l+1)

。

做完上面的跳跃后，一定可以只花一步就能到达

r

：

如果 $dp[x][0]\le l$ ，即从当前等效起点出发可以一步到达 $[l, r]$ 的所有点，那么答案增加 $r-l+1$ ，然后直接退出计算即可。

如果 $dp[x][0]>l$ ，答案增加 $r-dp[x][0]+1$ ，将等效起点转移到 $dp[x][0]$ 上，答案再增加 $dp[x][0]-l$ ，合起来还是增加 $r-l+1$ 。

但是接下来的部分怎么处理呢？由于接下来的连续的点全部都要到达恰好一次，我们可以定义

sum[i][j]

表示从

i

出发到达所有

j

步可达的点的总最短距离（包不包括

i

都没事，因为到自己的最短距离为

0

），同样是在

\text{Lemma 2}

的状态下。

转移方程如下：

sum[i][1] = i-dp[i][1]

sum[i][j+j'] = sum[i][j]+j'\times (dp[i][j]-dp[i][j+j'])+sum[dp[i][j]][j'], j, j'>1

中间的

j'\times (dp[i][j]-dp[i][j+j'])

是根据等效起点法得到的，请自行思考。

倍增优化后的转移方程如下；

sum[i][2^0] = i-dp[i][2^0]

sum[i][2^{j+1}]=sum[i][2^j]+2^j\times(dp[i][2^j]-dp[i][2^{j+1}])+sum[dp[i][2^j]][2^j], j>1

这样，我们可以继续套用同样的倍增方式：如果走

2^j

步仍未到达

i

，则走下这

2^j

步，然后答案增加

sum[x][2^j]

，等效移动起点到

dp[x][2^j]

，答案再增加

2^j\times(dp[x][2^j]-l)

。

最后还剩下一片散块，散块内的点全部可以一步从当前等效起点

x

到达，答案增加

x-l

，终于结束了！

代码

警示：

\sum\limits_{i=l}^rdist(x, i)

可能超出

\text{int32}

的范围，不仅仅是

sum

的定义，相关计算过程的每一项可能超出

\text{int32}

的表达式都要注意类型正确。

云剪贴板存档

AC 记录

CPP

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long int64;

int n, L[300001], q;   // 用大 L 区分询问小 l 

int s[300001];         // s[i] : L[i~n] 的最小值
int dp[300001][19];    // dp[i][j] : 从 i 出发走 j 步可达的最左端点 
int64 sum[300001][19]; // sum[i][j] : 从 i 出发到 j 步可达的所有点的最短距离和

void init(){
	s[n] = L[n];
	dp[n][0] = L[n];
	sum[n][0] = n-L[n];
	for(int i=n-1; i; --i){
		s[i] = min(s[i+1], L[i]); // 递推求 s 
		dp[i][0] = s[i];          // dp 的初始状态 
		sum[i][0] = i-dp[i][0];   // sum 的初始状态 
	}
	for(int j=1; j<=18; ++j){
		for(int i=1; i<=n; ++i){
			// dp 的倍增递推转移方程 
			dp[i][j] = dp[dp[i][j-1]][j-1];
			// sum 的倍增递推转移方程 
			sum[i][j] = sum[i][j-1]+sum[dp[i][j-1]][j-1]+(1ll<<(j-1))*(dp[i][j-1]-dp[i][j]);
		}
	}
}
int64 solve(int l, int r, int x){
	int64 ans = 0;
	// 处理第一步可达的点 
	if(L[x]<=r){ 
		if(L[x]<=l){    // 一步可以到达所有点 
			return r-l+1;
		}else{
			ans += r-L[x]+1;
			r = L[x]-1; // 从询问区间中删除交集 
		}
	}
	// 转移等效起点 
	ans += r-l+1;
	x = L[x];
	// 第一部分：r 所在的散块 
	for(int j=18; ~j; --j){
		if(dp[x][j]>r){
			ans += (r-l+1)*(1ll<<j);
			x = dp[x][j];
		}
	}
	ans += r-l+1;
	if(dp[x][0]<=l) return ans;
	// 第二部分：[l, r] 中间的完整块 
	x = dp[x][0];
	for(int j=18; ~j; --j){
		if(dp[x][j]>l){
			ans += sum[x][j]+(1ll<<j)*(dp[x][j]-l);
			x = dp[x][j];
		}
	}
	// 第三部分：l 所在的散块 
	ans += x-l;
	return ans;
}

int main(){
	scanf("%d", &n);
	L[1] = 1; // 注意 L[1] 要手动赋值 
	for(int i=2; i<=n; ++i) scanf("%d", L+i);
	init();
	scanf("%d", &q);
	while(q--){
		int l, r, x;
		scanf("%d%d%d", &l, &r, &x);
		int64 sum = solve(l, r, x), len=r-l+1;
		int64 gcd = __gcd(sum, len);
		printf("%lld/%lld\n", sum/gcd, len/gcd);
	}
	return 0;
}

题解：P5465 [PKUSC2018] 星际穿越

文章操作

题目分析

形式化题意

编码要求

暴力算法

正解 DP

引理 1

证明

引理 1.1

引理 1.2

引理 1.3

回归题目

引理 2

证明

DP 状态定义

求解答案

代码

相关推荐

评论

题解：P5465 [PKUSC2018] 星际穿越