神奇题目记录

这个系列用来做让我觉得耳目一新的题目或者是从来没有见过的 trick，也有可能是单纯觉得某个题目比较有意思，或者有启发性。

AGC001F

给定 的排列 ，可以无限次进行以下操作：

• 如果有 满足 且 ，可以交换 和 。

求得到的所有可能排列中字典序最小的排列。

。

Sol

首先，可以发现，我们是不好处理位置差大于 这种操作的，同时由于题目要求 才能操作，不妨又设一个排列 ，满足 。如此，操作就转化成了找到 ，使得 ，交换 。问题变成：求一个可能的操作后的排列 使得 中 的位置最靠前，然后使 中 的位置最靠前，以此类推。

考虑排序，贪心来讲，从小到大枚举每一个数 ，尽可能往左动，考虑经过路径上的数，一定都比 要大至少 ，因为小于 的话，让 排前面必然更劣。

那么考虑归并排序，右半部分指针所在数想要排在左半边的数之前，必然比左半边剩下的数都至少小 ，维护后缀最小值然后比较即可。