001f

特别有意思的思维题。 ### 思路 参考题解第一位的神仙思路。 将排列 $a_i$ 变为 $b_{a_i}$。 限制便变为了只能交换相邻的两个差大于 $k$ 的点。 那么这个限制就已经与普通排序很相似。 考虑使用归并排序。 一个点可以跑到其他点的前面要求这一连续段都是比它加 $k$ 都不大。 在归并 ......

首先题目给的限制条件很奇怪，下标差 $K$ 而值域差 $1$。我们变成逆排列，然后就转换成了下标差 $1$，值域差 $K$ 了，每次操作就相当于交换相邻的两个差 $\ge K$ 的数。 假设新的逆排列为 $Q_i$。我们发现，假如存在两个数差 $<K$，那么它们的相对位置关系一定不变。那么我们现在有 ......

考虑转化对所有能操作得到的$P$集合的判定。 求$P$的逆置换$Q$（交换下标和值），操作转化为：若$|Q_i-Q_{i+1}|\ge K$，可交换$i$和$i+1$。 这样转化交换的就是相邻两个位置的值，如果没有前面的限制，任何排列都可以被操作得到。 加上限制，显然有必要条件：数值对$(u,v)$ ......