P17139 [KOI 2026 #1] 跳跃

在二维坐标平面上有 $N$ 个踏板，编号为 $1$ 到 $N$。每个踏板都可以表示为坐标平面上的一个点。对于每个整数 $i$（$1 \le i \le N$），踏板 $i$ 的坐标为 $(X_i,i)$。 对于两个整数 $i,j$（$1 \le i,j \le N$），当且仅当以下两个条件均满足时，才能从踏板 $i$ 移动到踏板 $j$： - $i

第一行输入两个整数 $N$ 和 $D$，整数之间以空格分隔。 第二行输入 $N$ 个整数 $X_1,X_2,\ldots,X_N$，整数之间以空格分隔。

第一行输出 $N$ 个整数，整数之间以空格分隔。其中，第 $i$ 个整数表示从踏板 $i$ 出发，经过 $0$ 次或多次从一个踏板到另一个踏板的移动后，能够到达的不同踏板数量（$1 \le i \le N$）。

### 样例说明 1 对于每个踏板，从该踏板出发能够到达的踏板如下： - 踏板 $1$：能够到达包括踏板 $1$ 本身在内的所有踏板。 - 踏板 $2$：能够到达踏板 $2$、$3$、$4$、$6$。 - 踏板 $3$：能够到达踏板 $3$、$4$、$6$。 - 踏板 $4$：除踏板 $4$ 本身外，无法到达其他任何踏板。 - 踏板 $5$：能够到达踏板 $5$、$6$。 - 踏板 $6$：除踏板 $6$ 本身外，无法到达其他任何踏板。 ### 限制条件 - 输入中给出的所有数均为整数。 - $1 \le N \le 300\,000$。 - $1 \le D \le 10^9$。 - 对于每个整数 $i$（$1 \le i \le N$），均有 $1 \le X_i \le 10^9$。 ### 子任务 1. （$12$ 分）$N \le 300$。 2. （$32$ 分）$N \le 7\,500$。 3. （$9$ 分）$X_1 \le X_2 \le \cdots \le X_N$。 4. （$23$ 分）对于每个整数 $i$（$1 \le i \le N$），均有 $X_i \le 30$。 5. （$33$ 分）$D=1$。 6. （$41$ 分）无附加限制。 译注：没有单独的子任务 5 的测试点，所以子任务 6 有 $74$ 分。 翻译由 ChatGPT-5.6 完成