归并排序求逆序对

by mps

  【1】什么是逆序对？

      对于一个数列需要按从小到大排序，如果有ai,aj且满足ai>aj和i<j则ai,aj为一组逆序对

  【2】如何求逆序对？

       我们发现，我们可以暴力枚举i,j，然后逐一判断并累加答案即可，时间复杂度O(N²)

       但是对于数据量大一点的题目，只有不断地TLE了→_→

  【3】归并排序求逆序对

       逆序对的定义（见【1】）是一组本应该有序的序列中的逆序对，那么我们就想到了排序，但由于是要22匹配，我们又想到了归并排序

       归并排序大致内容如下：

             将一组数据先不断分割，直到分为一个一组，然后对于每个区间自小到大的进行有序表合并（O(N)），然后向上回溯，主体思想是分治

       我们发现，在合并的时候，如果出现有一组合并错误

（即不是直接A然后紧跟B，而是中间有一个ai并没有在正确的位置，被b中的一个数取代了，那就证明一定有mid-i+1个逆序对，因为前面一定是有序的）

       所以求逆序对本身非常简单，只需要写一个归并排序，在合并的过程中，如果并不是插入了A的元素，而是B的，则答案类加上mid-i+1

  【4】模板

1 void Union(int l,int mid ,int r){ 2     int i=l,j=mid+1,len=l-1; 3     while(i<=mid && j<=r) 4     { 5         if(a[i]<=a[j])b[++len]=a[i++]; 6         else { 7             b[++len]=a[j++]; 8             ans+=mid-i+1; 9             ans=ans%Mod;10         }11     }12     while(i<=mid)b[++len]=a[i++];13     while(j<=r)b[++len]=a[j++];14     for(i=l;i<=r;i++)a[i]=b[i];15 }16 17 void merge_sort(int l,int r){18     if(l
     
      >1;20         merge_sort(l,mid);21         merge_sort(mid+1,r);22         Union(l,mid,r);23     }24 }25 26 int main(){27   init();28   merge_sort(1,n);29   printf("%d",ans);30   return 0;31 }
     

  【5】总结

    该算法的时间复杂度由O(N²)降至O(NlogN)

    空间复杂度由O(1)升至O(N)

    空间换时间