题解：P5465 [PKUSC2018] 星际穿越
user100566
·
·
题解
很多题解仅仅把这道题的倍增优化 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
换句话说，我们可以认为从 $i$ 出发可以一步到达的点为 $[l_i, n]$ 内的所有点，而不改变答案。
#### 证明
*注：下面各子引理的证明比较废话，读者可自行画图理解*。
显然 $\text{Lemma 1}$ 只是增加了边而没有删除边，那么答案不会增大。
##### 引理 1.1
$\text{Lemma 1.1}$：**如果最短路径存在向右的传送，那么所有向右的传送不在任何向左的传送之后**。
证明：假设在某一步向右传送($b\rightarrow c$)，在向左传送($b\leftarrow a$)之后，有以下情况：
1. $c=a$：无需多言。
1. $c<a$：可得 $l_a\le b<c<a$，那么可以直接 $c\leftarrow a$，那么原路径就不是最短路径了。
3. $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$。
1. 若 $x=b$，无需多言。
2. 若 $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$，有以下情况：
1. $a=x$，无需多言。
2. $a<x$，有 $l_x\le a<x$，那么可以从 $x$ 出发传送到 $a$，无需向右传送。
3. $a>x$，对于存在的唯一一步 $b\xleftarrow{x}c$，满足 $b<x\le 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 记录
#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;
}