数据结构

首先显然要先把原数组重新映射一下，令映射过后的数组为 $a_i$ 因为题目要求 $|a_j - a_i| >= K$ 的可以置换，那么反之，则有 $|a_j - a_i| < K$ 的 $i, j$ 相对位置不变 故最简单的方法就是对于每个 $i$，将其与所有满足 $|a_j - a_i| < K$ 的 $j$ 连边，然后跑一边拓扑，复杂度 $O (n^2)$ 然后考虑在 $a_i$ 连的这么多边中，若是存在边 $(i, j), (j, k), (i, k)$，其中 $i < j < k$，那么显然 $(i, k)$ 的存在性是无关紧要的 又 $a_i$ 可连边的权值范围是 $(a_i - K, a_i) \cup (a_i, a_i + K)$，那么只需要分别向两个区间中标号最小的那个点连边就好了（单向边，并且一定向标号比自己大的点连），这样就相当于是将原来的乱七八糟连接的图变成了一条条单向的链，并且这些链可以覆盖原来的所有情况 代码1234567891011121314151617181920212223242526272829303132333435 ...