[AGC001F] Wide Swap 题解

特别有意思的思维题。

思路

参考题解第一位的神仙思路。

将排列 \(a_i\) 变为 \(b_{a_i}\)。

限制便变为了只能交换相邻的两个差大于 \(k\) 的点。

那么这个限制就已经与普通排序很相似。

考虑使用归并排序。

一个点可以跑到其他点的前面要求这一连续段都是比它加 \(k\) 都不大。

在归并上体现为序列的一段后缀。

那么我们只要统计后缀最小值即可。

Code

AC记录。