设计一个平均时间为 O ( n l o g n ) O(nlogn) O(nlogn)的算法，在 n ( 1 < = n < = 1000 ) n(1<=n<=1000) n(1<=n<=1000)个元素的数组中寻找逆序对数目
这里介绍分治的思想，用归并对数组进行排序，在排序的过程中，即可顺便将逆序对数目求出来
首先，不断地二分这个数组，直到最小，然后归并两边
归并时，需要注意的是两边的数组一定是顺序的，因为二分数组已经到最小了，同时，返回后，以后归并时两边刚好是之前已经排好序的部分
同时遍历一遍左右两边，用 i i i 和 j j j 当做两边遍历的指针，用 k k k 作为排序好的数组的指针
由于两边都是排好序的，所以对每个 i i i ，当 a [ i ] > a [ j ] a[i] > a[j] a[i]>a[j]，第 i i i 个到第 m i d mid mid 个（左边剩余的元素）与第 j j j 个都满足逆序，记录到 a n s ans ans 中，将 a [ j ] a[j] a[j]记录到新数组中， j + + j++ j++
两边遍历结束之后，若有一边（ i i i 或 j j j ）还没有遍历完，则直接将剩余的元素记录到新数组中，因为这些元素肯定都是最大的，并且我们也已经记录了其中逆序的情况（不论是 i i i 还是 j j j ）
最后排好序的数组变成原数组，完成这一次归并与逆序的统计
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int ans;void merge(int a[], int l, int mid, int r) {int i=l, j=mid+1, k=l, temp[10010];while ((i<=mid) && (j<=r))if (a[i] <= a[j]) temp[k++] = a[i++];else {temp[k++] = a[j++];ans += mid-i+1;}if (i > mid)for(int q=j; q<=r; q++) temp[k++] = a[q];elsefor(int q=i; q<=mid; q++) temp[k++] = a[q];for(int p=l; p<=r; p++) a[p] = temp[p];
}void merge_sort(int a[], int l, int r) {if(l >= r) return;else {int mid = (l + r) / 2;merge_sort(a, l, mid);merge_sort(a, mid+1, r);merge(a, l, mid, r);}
}int main() {int n, a[10010];scanf("%d", &n);for(int i=0; i<n; i++) scanf("%d", a+i);merge_sort(a, 0, n-1);printf("%d\n", ans);
}