CF1375E Inversion SwapSort

题意：给定一个长度为 的序列 ，构造 中的所有逆序对 的一个排列 ，

使得依次交换 后序列单调不降。

可以证明一定存在解。

，，时限 。

---

有意思的题。

先考虑 为排列的情况。

我们知道，冒泡排序的交换次数恰好为逆序对数，且每次交换都在操作一个逆序对。

于是，尝试构造冒泡排序与本题方案的对应。

设 为值 在 中的出现位置，对 进行冒泡排序。

当相邻的 交换时，相当于交换了 ，而不难发现他们原来也必然是一组逆序对。

由于交换次数等于逆序对数且不会将同一对 交换两次，故没有漏掉任何一组逆序对。

当 有序后，显然 也是有序的。

若原数组不是排列，则按值为第一关键字，位置为第二关键字，即可等价地去掉相等元素。

复杂度 。