《算法导论》部分习题和思考题解答: 2-4 逆序对

设A[１．．ｎ]是一个包含哪个不同数的数组。如果在ｉ＜ｊ的情况下，有Ａ[i] > A[j]，则称 (i, j) 为A中的一个逆序对(inversion)。给出一个算法，他能用O(nlgn)的最坏情况运行时间，确定n个元素的任何排序中逆序对的数目。

按照题目的提示，可以更改合并排序的程序来求逆序对的数目。在merge的过程中，如果右数组的当前元素小于左数组的当前元素，则该右数组当前元素和左数组当前元素及所有后面的元素都形成逆序对。因此只要把当前左数组元素的数量累加到一个变量中，即可求出本次merge的逆序对的数量。总的逆序对数量是每次便利的左右数组逆序对数量及merge的逆序对数量之和。程序如下所示：

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <string>
#include <sstream>
#include <math.h> 
#include <string.h>
#include <algorithm>
#include <numeric>
#include <deque>
#include <climits>
#include <iomanip>
#include <unordered_map>
#include <iterator>
#include <list>
#include <chrono>
#include <unordered_set>

using namespace std;

template<class T>
void readVector(vector<T>& v, int n) {
	for (int i = 0; i < n; i++) {
		cin >> v[i];
	}
}

int merge(vector<int>& v, int l, int r) {
	int ans = 0, m = l + (r - l) / 2;

	vector<int> vl(v.begin() + l, v.begin() + (m + 1)); vl.push_back(INF);
	vector<int> vr(v.begin() + (m + 1), v.begin() + (r+1)); vr.push_back(INF);

	int il = 0, ir = 0;
	for (int i = l; i <= r; i++) {
		if (vl[il] <= vr[ir]) {
			v[i] = vl[il++];
		}
		else {
			v[i] = vr[ir++];
			if (il != (vl.size() - 1)) // sentinal card is excluded
				ans += vl.size() - 1 - il;
		}
	}

	return ans;
}

int mergeSort(vector<int>& v, int l, int r) {
	int ans = 0;

	if (r > l) {
		int m = l + (r - l) / 2;

		ans += mergeSort(v, l, m);
		ans += mergeSort(v, m + 1, r);
		ans += merge(v, l, r);
	}

	return ans;
}

int main() {
	multiset<int> ms; 

	int n; cin >> n; 
	vector<int> v(n);
	readVector(v, n);

	int ans = mergeSort(v, 0, n - 1);

	cout << ans << endl;
	

	return 0;
}