逆序对

对于一个数列a[],比如说:5 3 4 2 1;

我们可以将其离散化成b[],先在位置5加1,然后在位置3加1,然后在位置4加1,以此类推;

当在一个位置x加1时,b[]中已经加完的的值保证了其l<r;

那么如何统计a[l]>a[r]的个数呢? 这个个数就是sum(b[1]~b[x]);

到这里求得方法已经完事了,时间复杂度O(n^2);

那么优化呢?

我们可以发现,sum()的性质和十分可爱的树状数组十分相似,那么我们可以用树状数组来统计sum()

这样时间复杂度就变为了O(nlogn);

注意:当有重复元素存在时,可以使用stable_sort()来排序。

stable_sort())可以保证相等元素的原本相对次序在排序后保持不变。

原文地址:https://www.cnblogs.com/kamimxr/p/11285238.html