[AdditionalFile4810.zip](file://AdditionalFile4810.zip?type=additional_file)

#4810. 「RMI 2024」Jump Civilization

标签: 传统 | 时间限制: 1000 ms | 内存限制: 512 MiB |

题目描述

题目译自 Romanian Master of Informatics 2024 Day2 T3 「Jump Civilization」

「Here in Parkour Jump Civilization, No One Chooses to Jump for the Beef」—— Evbo -《跑酷文明》电影

在跑酷文明的世界里，有 $N$ 个漂浮的岛屿，编号从 $1$ 到 $N$。当你站在岛屿 $i$ $(1 \leq i < N)$ 上，你可以选择：

• 简单跳跃：从岛屿 $i$ 跳到旁边的岛屿 $i + 1$；
• 困难跳跃：从岛屿 $i$ 跳到岛屿 $v_i$，其中 $i < v_i \leq N$。

为了在跑酷文明中提升等级，你需要计算每个岛屿的跳跃能力。岛屿 $i$ 的跳跃能力是指从岛屿 $i$ 开始，最多使用 $K$ 次跳跃能够到达的岛屿数量。

上一任跳跃冠军为了确保跳跃路线的公平性，设定了一条重要规则：对于任意 $1 \leq i < j \leq N$，要么 $v_i \leq j$，要么 $v_j \leq v_i$。

作为跑酷文明的一员新手，你希望高效地算出每个岛屿的跳跃能力——你能做到吗？

输入格式

输入的第一行包含两个空格分隔的整数 $N$ 和 $K$。

第二行包含 $N - 1$ 个空格分隔的整数 $v_1, \dots, v_{N-1}$，表示每个岛屿的困难跳跃目标。

输出格式

输出一行，包含 $N$ 个空格分隔的整数，按顺序表示每个岛屿的跳跃能力。

样例 1

输入

5 1
4 3 4 5

输出

3 2 2 2 1

从岛屿 $1$ 开始：

• 不跳跃，可以到达岛屿 $1$；
• 跳跃一次，可以到达岛屿 $2$（简单跳跃）或岛屿 $4$（困难跳跃）。

总共能到达 $3$ 个岛屿，因此岛屿 $1$ 的跳跃能力是 $3$。

样例 2

输入

6 2
2 3 5 5 6

输出

3 4 4 3 2 1

数据范围与提示

对于所有输入数据，满足：

• $1 \leq N \leq 300 \ 000$
• $1 \leq K \leq N - 1$
• $i < v_i \leq N$
• 对于 $1 \leq i < j \leq N$，满足 $v_i \leq j$ 或 $v_j \leq v_i$。
• 如果从岛屿 $i$ 出发，通过两种不同路径在最多 $K$ 次跳跃内都能到达岛屿 $j$，在计算岛屿 $i$ 的跳跃能力时，岛屿 $j$ 只计数一次。
• 计算跳跃能力时，跳跃类型（简单或困难）不重要，只看跳跃次数。

详细子任务附加限制及分值如下表所示。