hdoj3743——归并排序求逆序数

在学线段树的时候遇到逆序数的题,先巩固下归并排序和逆序数。

逆序对:数列a[]中,a[i]>a[j](i

逆序数:一个数列中逆序对的对数称为逆序数。

归并排序求逆序数(nlog(n)):

       在归并排序的二路合并阶段(显然合并是自底向上的,所以可以保证合并时两个序列分别有序),如果第二个序列的当前值小于第一个数列的当前值,则显然前一个数列当前值到第一个数列结尾的元素和第二个序列的当前值构成逆序对。描述得有些不好,见代码。

为什么通过不断求两个子序列间的逆序数可以最终得到原数列的逆序数?

答:因为归并排序的分治后,在合并阶段,子序列间元素的相对位置没有改变。这个比较难表达,要自己体会。

例如:a[i]在数列one中,a[j]在数列two中,假设a[i]>a[j]并且one在前,two在后,现在已经求出了one的逆序数(通过合并one的两个子数列),求出了two的逆序数,即one和two都排成有序了,接下来要将one和two合并。显然a[i]和a[j]的相对位置还是没变。仍然构成逆序对。

说白了就一句话,子数列的排序并不影响父数列中元素的逆序关系。因而不断求出小范围内的逆序数,再不断扩大范围就可以最终求出总的逆序数。好了,这样就“证明”了归并排序求逆序数的正确性。

接下来还有一个问题:如果规定为使数列升序,只能通过交换相邻元素实现,那么交换次数和该数列逆序数的关系?

答:交换次数=逆序数

为什么呢?很简单,基于以下三点:

(1)逆序的数必须交换

(2)一次交换只能改变两个数的逆序关系

(3)如果两个数逆序,则必然需且仅需1次交换。

也就是说通过一次交换可以使1个逆序对消失。这样结论就很清楚了。。

总结:我想通过归并不仅可以求逆序数,题目改变一下也是可以做的,如要找出a[i]+b*i-c>a[j]+b*j-c(i<j)的对数,那么通过小小修改,或是对原数列进行预处理就行了。关键是理解本质。。想了这些之后,我自己的思路也理清了,轻松不少。(当然自己的思绪还是有错误的地方)

下面放上代码(顺便作为自己以后解题的模板):