CF689B Mike and Shortcuts

最近，Mike 正忙于备考和参加比赛。现在他打算放松一下，在城市里四处游览。 城市由 $n$ 个编号从 $1$ 到 $n$ 的交叉路口组成。Mike 从他家所在的第 $1$ 个交叉路口出发，沿着一些交叉路口依次行走。从第 $i$ 个交叉路口走到第 $j$ 个交叉路口需要消耗 $|i-j|$ 的能量。Mike 访问交叉路口序列 $p_1 = 1, p_2, ..., p_k$ 所需的总能量是 $\sum\limits_{i=1}^{k-1}|p_i - p_{i+1}|$ 单位能量。 当然，如果没有捷径，走路就太无聊了。捷径是一种特殊的路径，允许 Mike 仅消耗 1 单位能量就可以从一个交叉路口走到另一个交叉路口。Mike 的城市里恰好有 $n$ 条捷径，第 $i$ 条捷径允许从交叉路口 $i$ 走到交叉路口 $a_i$（$i \le a_i \le n$）（但不能反向行走），也就是说，每个交叉路口恰好有一条捷径起始于它。形式上，如果 Mike 选择的序列为 $p_1 = 1, p_2, ..., p_k$，对于所有满足 $1 \le i$ 且 $p_{i+1} = a_{p_i}$ 且 $a_{p_i} \ne p_i$ 的情况，Mike 只需消耗 1 单位能量来从交叉路口 $p_i$ 到 $p_{i+1}$。例如，如果 Mike 选择的序列是 $p_1 = 1, p_2 = a_{p_1}, p_3 = a_{p_2}, ..., p_k = a_{p_{k-1}}$，那么他将总共消耗 $k - 1$ 单位能量。 在开始这段旅行之前，Mike 想知道从他家到每个交叉路口所需的最小能量。形式上，对于每个 $1 \le i \le n$，Mike 想要知道从交叉路口 1 到交叉路口 $i$ 所需的最小可能总能量。

第一行一个整数 $n$ $(1 \le n \le 200000)$ — 表示城市的交叉路口数量。 第二行包含 $n$ 个整数 $a_1, a_2, ..., a_n$ $(i \le a_i \le n)$，表示城市的捷径。第 $i$ 个捷径允许从交叉路口 $i$ 到交叉路口 $a_i$ 走捷径，仅消耗 1 单位能量。请注意捷径不可逆（不能从 $a_i$ 走到 $i$）。

输出一行 $n$ 个整数 $m_1, m_2, ..., m_n$，其中 $m_i$ 表示从交叉路口 $1$ 到交叉路口 $i$ 所需的最小总能量。

在第一个样例中，最优路径为： - 到 1: 仅为起点，$m_1 = 0$； - 到 2: $1 \to 2$，$m_2 = 1$； - 到 3: $1 \to 3$，$m_3 = |3 - 1| = 2$。 在第二个样例中，每个交叉路口 $i$ 都可以直接从 $1$ 走过去，$m_i = |1 - i|$。 在第三个样例中，考虑以下路径： - 到 1: $m_1 = 0$； - 到 2: $1 \to 2$，$m_2 = 1$； - 到 3: $1 \to 4 \to 3$，$m_3 = 1 + |4 - 3| = 2$； - 到 4: $1 \to 4$，$m_4 = 1$； - 到 5: $1 \to 4 \to 5$，$m_5 = 1 + |4 - 5| = 2$； - 到 6: $1 \to 4 \to 6$，$m_6 = 1 + |4 - 6| = 3$； - 到 7: $1 \to 4 \to 5 \to 7$，$m_7 = 1 + |4 - 5| + 1 = 3$。 翻译由 GPT-4o 生成。