求逆序对数目___O(nlogn) —— 分治 归并

    设计一个平均时间为$O(nlogn)$的算法，在$n(1<=n<=1000)$个元素的数组中寻找逆序对数目

    这里介绍分治的思想，用归并对数组进行排序，在排序的过程中，即可顺便将逆序对数目求出来

    首先，不断地二分这个数组，直到最小，然后归并两边
    归并时，需要注意的是两边的数组一定是顺序的，因为二分数组已经到最小了，同时，返回后，以后归并时两边刚好是之前已经排好序的部分
    同时遍历一遍左右两边，用 $i$ 和 $j$ 当做两边遍历的指针，用 $k$ 作为排序好的数组的指针
    由于两边都是排好序的，所以对每个 $i$ ，当$a[i]>a[j]$，第 $i$ 个到第 $mid$ 个（左边剩余的元素）与第 $j$ 个都满足逆序，记录到 $ans$ 中，将$a[j]$记录到新数组中，$j++$

    两边遍历结束之后，若有一边（ $i$ 或 $j$ ）还没有遍历完，则直接将剩余的元素记录到新数组中，因为这些元素肯定都是最大的，并且我们也已经记录了其中逆序的情况（不论是 $i$ 还是 $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];
	else
		for(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);
}