首页 > 代码库 > 逆序对

逆序对

逆序对就是说在一个集合里边满足i<j && a[i]>a[j]的一对元素(或者a[i]<a[j],也可以是|,∈等其他奇奇怪怪的偏序)(一般还是>和<用的多)

当定义逆序对的偏序是>的时候逆序对个数的意义就是给这些数升序冒泡最少交换的次数

为什么呐

如果i<j && a[i]<a[j],呢么这两个数可以“平行”地移过去而不进行交换,反之如果a[i]>a[j],呢么a[i]要往右走,a[j]要往左走,但是a[i]又在a[j]的左边,这两个数一定会相遇,就不可避免地要交换

怎么求呐

可以使用归并排序,在合并的时候就将逆序对的个数计算出来

核心思想就是在合并的时候,如果a[i]>a[j],呢么一直到归并的中间点都是逆序对,归并的两半都已经单调递增了,a[i]比a[j]大,a[i+1~mid]也一定比a[j]大

代码:

技术分享
 1 int c[110000]; 2 int d[110000],dtou=0; 3 int bowl=0; 4 void bing(int _left,int _right){ 5     int mid=(_left+_right)/2;  dtou=_left-1; 6     int i=_left,j=mid+1; 7     while(i<=mid && j<=_right){ 8         if(c[j]<c[i]){  d[++dtou]=c[j++];  bowl=(bowl+mid-i+1)%mo;} 9         else  d[++dtou]=c[i++];10     }11     while(i<=mid)  d[++dtou]=c[i++];//序列是单调的,所以后面的肯定也都大于前面的12     while(j<=_right)  d[++dtou]=c[j++];13     for(int i=_left;i<=_right;i++)14         c[i]=d[i];15 }16 void gui(int _left,int _right){17     if(_left<_right){18         int mid=(_left+_right)/2;19         gui(_left,mid),gui(mid+1,_right);20         bing(_left,_right);21     }22 }
View Code

 

逆序对