【AGC001F】Wide Swap

令\(i\)的位置为\(Q_i\)：

从这个角度考虑问题和给定的操作，就是每次交换相邻的两个数，并且它们要满足差不小于\(k\)，使得最终\(1\)的位置尽量靠前，然后\(2\)的位置尽量靠前，依此类推。

可以发现差小于\(k\)的数的相对位置不会发生变化，并且满足这个条件的排列都是合法排列。

另外可以证明的是最小字典序的\(Q\)一定对应最小字典序的\(P\)。求出最小字典序后在\(i\)前面的数一定都是比\(i\)小或者比\(i\)大且差小于\(k\)且在原来\(Q\)中就在\(i\)前面的数。这样就保证了\(i\)在不比它小的数中尽可能靠前，就得到了最小字典序的\(P\)。

那么如果\(|i-j|<k\)并且\(P_i<P_j\)那么从\(i\)向\(j\)连边，求这张图的最小字典序拓扑排列即可。

边数\(O(n^2)\)，考虑优化。每个点只需要连向左右最小的满足条件的数即可，其它的边实际上不需要。