ARC102D Revenge of BBuBBBlesort!

记录：给定长度为 的排列 , 可以进行任意次如下操作：

• 选择 使得 且 . 交换 。

判定最终能否将其排成升序。

，时限 。

---

某次操作完成后，从 变为 。

整个序列的逆序对个数减少了 个。

又能发现，奇偶性不同的位置无法互相移动，故要将奇偶分别取出，判定是否都为 奇数/偶数。

又能发现，每次操作中，奇数部分或偶数部分的逆序对减少 。

这得出一个必要条件：奇数部分和偶数部分的逆序对的和是整个排列的逆序对的 。

下面证明上述条件同时也是充分的。

记整个排列的逆序对个数为 ，奇数部分得逆序对个数为 ，偶数部分的逆序对个数为 。

对奇数部分和偶数部分进行冒泡排序，共有 次交换。

这些交换完成后，整个序列都是有序的，故逆序对个数减少了 。

每次操作中逆序对个数至多减少 ，由于 ，故每次操作中逆序对个数的减少量都达到上界，也都满足操作所需的条件。

需要求逆序对，复杂度为 。