归并排序

求逆序对我用的是归并排序

直接上我在洛谷里做的那道逆序对的题目的归并排序主要代码吧

 1 void msort(int l, int r) {
 2     if (l >= r)return;
 3     int mid = (l + r) >> 1;
 4     msort(l, mid);
 5     msort(mid + 1, r);
 6     int i = l, j = mid + 1, k = l;
 7     while (i <= mid && j <= r) {
 8         if (a[i] >a[j]) {
 9             b[k++] = a[j++];
10             ans += (mid - i + 1);
11             //cout << a[i] << " " << a[j] << endl;
12         }
13         else b[k++] = a[i++];
14     }
15     while (i <= mid)b[k++] = a[i++];
16     while (j <= r)b[k++] = a[j++];
17     for (int i = l; i <= r; i++)a[i] = b[i];
18 }

ans就是最终逆序对的数量啦！