codeforces-GlobalRound9-E
题意
给出一个长度为n的数组a
要求对它进行排序
排序的要求是只能使用原数组中逆序对下标的位置进行swap
比如原数组第u位和第v位形成逆序对 那么只能对数组的第u位和第v位进行swap
新数组中可能有新的逆序对第x位和第y位 但不能swap(ax,ay)
而且要用到所有逆序对下标 且只能用一次 (感觉怪怪的这不就直接等于逆序对?)
要求给出一种swap顺序使得最终的数组非降序
或者说
求一种将每个原数组中的逆序对下标 (u,v) 的排列，使依次交换每个 (au,av) 后，ai 不减
考虑a 是一个排列时怎么做。
我们设pos[v] 表示v 这个数在a 里出现的位置。也就是pos[a[i]]=i
从边界入手，我们先尝试把nn 放到排列的最后一个位置，然后转化为规模减11 的子问题。具体来说，假设一波操作后，我们得到的排列为bb ，则bb 需要满足如下条件：
- b[n]=nb[n]=n 。
- ∀1≤i,j<n 如果a[i]<a[j] ，则b[i]<b[j] 。
- ∀1≤i,j
a[j] ，则b[i]>b[j] 。 也就是说，要保证前面的数的相对大小关系不变，这样才能转化为一个等价的子问题。
我们怎么做呢？可以依次操作：交换(pos[a[n]+1],n) ,(pos[a[n]+2],n) ,(pos[a[n]+3],n) ,……,(pos[n],n) 。 交换操作(indx , indx)
具体的
比如原数组 ：5 4 2 1 3
第一次交换 pos[a[5]+1]=pos[4]=2 与 数组中第n个数交换
交换结果为 : 5 3 2 1 4
假设原数组中最大的数n不在位置n , 那么a[n]+1一定小于n 且显然a[n]+1>a[n]
那么数a[n]+1与a[n]显然构成逆序对
容易发现，这样一轮操作完成后，首先，n 被放到了最后。同时，前面所有大于a[n] 的数，相当于集体减1 ，显然前面所有数的相对大小关系不变。并且，我们恰好用掉了所有包含（位置）n 的逆序对。所以剩下的是一个规模减1 的子问题，继续做，直到n=1 即可。
于是我们就解决了排列的情况。相当于我们用构造的方法证明了，a 是一个排列时，一定有解。
再考虑不是排列的时候。对于两个相等的数a[i]=a[j] (i<j )，我们强行令a[i]<a[j] ，也就是以数值为第一关键字，位置为第二关键字，强行转成一个排列。发现转成排列后，序列里的逆序对和原来是一样的，所以直接按排列求解即可。
时间复杂度O(n2)