题目链接pta 题解：在归并排序基础上，添加判断左边节点和右边节点大小关系，共享逆序数对，因为归并排序，当前左边右边已经有序，需要呈递增，题目问的是左边大于右边个数，递减才能保证某个数左边都大于当前，判断做左边是否大于右边，大于则左边到mid的所有都大于右边这个数，上面说的递增，故多出了mid-i+1个逆序数对，右边那个被排序进去就可以看右边下一个了。 这样一次计算出来的都是当前这个区间里面的，下一层递归这个区间会被看成一个整体，就是类似当前的一个左边或者右边，所以不会出现重复的情况。
#include<iostream> #include<algorithm> using namespace std; int a[100000 + 100]; int b[100000 + 100]; int n; long long sum = 0; void meager(int l, int mid, int r) { int i = l; int j = mid + 1; //memset(b, 0, sizeof(b)); int cnt = 0; while (i <= mid && j <= r) { if (a[i] < a[j]) { b[cnt] = a[i]; i++; } else { b[cnt] = a[j]; sum += mid - i + 1; j++; } cnt++; } if (i <= mid) { for (; i <= mid; i++) { b[cnt] = a[i]; cnt++; } } if (j <= r) { for (; j <= r; j++) { b[cnt] = a[j]; cnt++; } } for (int k = l,x=0; k <= r; k++,x++) { a[k] = b[x]; } } void mersort(int l, int r) { if (l >= r)return; int mid; mid = (l + r) >> 1; mersort(l, mid); mersort(mid + 1, r); meager(l, mid, r); } int main() { cin >> n; for (int i = 1; i <= n; i++)cin >> a[i]; mersort(1, n); cout << sum; return 0; }最后：sum要开long long。。。。
