求排列的逆序数(分治)

考虑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(n2)

分治O(nlogn)：

1） 将数组分成两半，分别求出左半边的逆序数和右半边的逆序数

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

由归并排序改进得到，加上计算逆序的步骤

MergeSortAndCount: 归并排序并计算逆序数

代码：

#include
using namespace std;
#define N 100000 + 5
int n; 
int a[N];
int b[N];
int ans = 0;
void merge(int L, int R) {int mid = (L + R) / 2;int l = L;int r = mid+1;int count = 0;while(l <= mid && r <= R) {if(a[l] < a[r]) {b[count++] = a[r++];    } else {b[count++] = a[l++];ans += R - r + 1;}}while(l <= mid) b[count++] = a[l++];while(r <= R) b[count++] = a[r++];for(int i = L; i <= R; i++) a[i] = b[i-L];
}
void MergeSortAndCount(int L, int R) {if(L < R) {int mid = (L + R) / 2;MergeSortAndCount(L, mid);MergeSortAndCount(mid + 1, R);merge(L, R);}
}
int main() {scanf("%d", &n);for(int i = 0; i < n; i++) scanf("%d", &a[i]);MergeSortAndCount(0, n-1);printf("%d
", ans);return 0;
}