题解：P17139 [KOI 2026 #1] 跳跃
chen_zhe
·
·
题解
子任务 1
将给定的 N 个踏板视为图中的顶点。对于所有能够从踏板 i 移动到踏板 j 的有序对 (i,j)，添加一条从顶点 i 指向顶点 j 的边，即可构造出一张有向图。题目所要求的答案，就是从每个顶点出发能够到达的顶点数量。
对于每一对顶点 (i,j)，可以在 O(1) 时间内判断是否存在一条从 i 指向 j 的边。因此，可以在 O(N^2) 时间内构造出整张图。随后，对于每个顶点，可以使用 DFS 等图搜索算法，在 O(N^2) 时间内求出从该顶点出发能够到达的顶点集合。
因此，总时间复杂度为 O(N^3)。
子任务 2
将从踏板 i 出发能够到达的踏板集合按照如下方式分类：
考虑某个满足 R_i\ne\varnothing 的踏板 i，并令 k 为集合 R_i 中的最小元素。
对于任意元素 j\in R_i，下列两种情况中恰有一种成立。
因此，可以得到如下观察：
集合 R_i 中的每个元素恰好属于以下两类之一：
- 集合 R_k；
- 所有满足 i<j 且 X_i<X_j\le X_k 的踏板 j 所构成的集合。
对于集合 L_i，也可以得到类似的观察。
当 L_i\ne\varnothing 时，令 k 为集合 L_i 中的最小元素。那么，集合 L_i 中的每个元素恰好属于以下两类之一：
- 集合 L_k；
- 所有满足 i<j 且 X_k\le X_j<X_i 的踏板 j 所构成的集合。
利用上述观察，按照 i=N,N-1,\ldots,1 的顺序，可以对每个 i 在 O(N) 时间内求出 R_i、L_i 和 M_i。
因此，可以在总时间复杂度 O(N^2) 内解决本题。
子任务 3
如果能够从踏板 i 到达踏板 j，那么一定存在一条依次经过踏板 i,i+1,\ldots,j 的路径。因此，可以分为以下两种情况：
- 能够从踏板 i 移动到踏板 i+1：在这种情况下，从踏板 i 出发能够到达的踏板，就是从踏板 i+1 出发能够到达的所有踏板，再加上踏板 i 本身。
- 无法从踏板 i 移动到踏板 i+1：在这种情况下，无法从踏板 i 移动到其他任何踏板。
因此，可以按照 N,N-1,\ldots,1 的顺序求出每个踏板的答案。总时间复杂度为 O(N)。
子任务 4
令 X=\max\{X_1,X_2,\ldots,X_N\}。定义 S_x 为所有满足 X_i=x 的踏板编号 i 所构成的集合。可以在 O(N+X) 时间内求出所有集合 S_x。对于每个 i，集合 R_i 中的最小元素 k，就是集合 S_{X_i+1},S_{X_i+2},\ldots,S_{\min\{X,X_i+D\}} 中所有大于 i 的元素里的最小值。
对于每个集合 S_x，可以使用二分查找，在 O(\log N) 时间内找到其中大于 i 的最小元素。因此，可以在 O(X\log N) 时间内求出 k。
此外，也可以使用相同的方法，在 O(X\log N) 时间内求出满足 X_i<X_j\le X_k 且 i<j 的踏板 j 的数量。因此，按照 i=N,N-1,\ldots,1 的顺序，可以对每个 i 在 O(X\log N) 时间内求出 |R_i|。
使用相同的方法，也可以在相同的时间复杂度内求出 |L_i|。
对于 M_i，只需要计算满足 i\le j 且 X_i=X_j 的踏板数量。也就是说，|M_i| 等于集合 S_{X_i} 中大于或等于 i 的元素数量。该值可以使用二分查找在 O(\log N) 时间内求出。
因此，总时间复杂度为 O(NX\log N)。
子任务 5
按照子任务 4 中的方式定义 S_x。对于每个 i，集合 R_i 中的最小元素 k，就是集合 S_{X_i+1} 中大于 i 的最小元素。
由于给定的坐标值范围很大，可以使用 std::map 等数据结构管理所有集合 S_x，从而在 O(\log N) 时间内求出 k。
此外，如果某个踏板 j 满足 X_i<X_j\le X_k 且 i<j，那么必有 X_j=X_k。满足这一条件的 j 的数量也可以在 O(\log N) 时间内求出。
因此，按照 i=N,N-1,\ldots,1 的顺序，可以对每个 i 在 O(\log N) 时间内求出 |R_i|。
使用类似的方法，也可以在相同的时间复杂度内求出 |L_i| 和 |M_i|。因此，总时间复杂度为 O(N\log N)。
子任务 6
按照 i=N,N-1,\ldots,1 的顺序求出 |R_i|。
对于踏板 i，集合 R_i 中的最小元素 k，就是当前已经考虑过的踏板，即踏板 i+1,\ldots,N 中，坐标大于 X_i 且不超过 X_i+D 的所有踏板里，编号最小的踏板。
因此，可以使用线段树维护这些信息，并在 O(\log N) 时间内求出 k。由于踏板坐标的取值范围很大，还需要使用坐标压缩等方法。
集合 R_i 由集合 R_k 与所有满足 X_i<X_j\le X_k 且 i<j 的踏板 j 构成。属于第二类的踏板数量，等于当前已经考虑过的踏板中，坐标大于 X_i 且不超过 X_k 的踏板数量。
同样地，只要使用线段树维护当前已经考虑过的踏板集合，就可以在 O(\log N) 时间内求出这一数值。
可以使用相同的方法求出 |L_i|，而 |M_i| 则可以使用子任务 5 中的方法，在相同的时间复杂度内求出。
因此，总时间复杂度为 O(N\log N)。
翻译由 ChatGPT-5.6 完成