求排列的逆序数

考虑1,2,…,n (n <= 100000)的排列i1，i2，…，in，如果其中存在j,k，满足 j < k 且 ij > ik， 那么就称(ij,ik)是这个排列的一个逆序。
一个排列含有逆序的个数称为这个排列的逆序数。例如排列 263451 含有8个逆序(2,1),(6,3),(6,4),(6,5),(6,1),(3,1),(4,1),(5,1)，因此该排列的逆序数就是8。

现给定1,2,…,n的一个排列，求它的逆序数。

分治O(nlogn)：
1） 将数组分成两半，分别求出左半边的逆序数和右半边的逆序数
2） 再算有多少逆序是由左半边取一个数和右半边取一个数构成(要求O(n)实现）

2) 的关键：左半边和右半边都是排好序的。比如，都是从大到小排序的。这样，左右半边只需要从头到尾各扫一遍，就可以找出由两边各取一个数构成的逆序个数

代码如下：

#include <iostream>

using namespace std;

const int maxn = 1000005;

long long a[maxn];
long long t[maxn];

void merge_sort_and_count(long long a[], int s, int e, long long t[]);

void merge(long long a[], int s, int m, int e, long long t[]);

long long count = 0;

int main() {
	int times;
	cin >> times;
	for(int i = 0; i < times; i++) {
		count = 0;
		int n;
		cin >> n;
		for(int j = 0; j < n; j++) {
			cin >> a[j];
		}
		merge_sort_and_count(a, 0, n - 1, t);
		cout << count << endl;
	}
	return 0;
} 

void merge_sort_and_count(long long a[], int s, int e, long long t[]) {
	if(s >= e) {
		return;
	}
	int m = s + (e - s) / 2;
	merge_sort_and_count(a, s, m, t);
	merge_sort_and_count(a, m + 1, e, t);
	merge(a, s, m, e, t);
}

void merge(long long a[], int s, int m, int e, long long t[]) {
	int pt = 0;
	int pa = s;
	int pb = m + 1;
	while(pa <= m && pb <= e) {
		if(a[pa] <= a[pb]) {
			t[pt++] = a[pa++];
		} else {
			count += pb - (s + pt);
			t[pt++] = a[pb++];
		}
	}
	while(pa <= m) {
		t[pt++] = a[pa++];
	}
	while(pb <= e) {
		t[pt++] = a[pb++];
	}
	for(int i = 0; i < pt; i++) {
		a[s+i] = t[i];
	}
}

事实上稍懂归并排序的人都知道，其实就在merge函数里面加了一行

count += pb - (s + pt);

这一行是用来计算 2） 再算有多少逆序是由左半边取一个数和右半边取一个数构成(要求O(n)实现）

这个数字原本应该在的位置是(s+pt)，实际在的位置是pb，而本来在它右边的数字依然会在它右边，应该在它右边却在它左边的数字就与这个数字构成了一对逆序数。