题目链接：

题意：

给出一个序列，可以相邻的交换k次，求 k 次之后，逆序数对最少是多少；

 

分析：

可以发现，无论怎么交换之后，总共的逆序数对只会-1，那么结果就是，将这个序列排整齐时，要两两交换的次数-k；题目就转换为求这个序列的逆序数对有多少；

这样的两两交换好像是冒泡排序，冒泡排序是O(n^2)；

正确解法是归并排序；当我们合并两个有序序列时，如果，要将后面的插入到前一个中间，那么这里就有m-i+1个逆序数对；

1 #include 
      
        2  3 using namespace std; 4  5 const int maxn = 1e5 + 5; 6  7 __int64 cnt,k; 8 int a[maxn],c[maxn]; 9 10 11 void merge(int* a,int first,int mid,int last,int* c) {12     int i = first,j=mid+1;13     int m = mid,n=last;14     int k = 0;15     while(i<=m||j<=n) {16         if(j>n||(i<=m&&a[i]<=a[j])) {17             c[k++] = a[i++];18         }19         else {20             c[k++] = a[j++];21             cnt += (m-i+1);22         }23     }24     for(i=0;i