Posted in Divide and Conquer

PKU 5 Reversed pairs

Problem: http://acmicpc.openjudge.cn/practice/005/


#include<iostream>
using namespace std;
int a[100005] = {0};
int tmp[100005] = {0};
long long cnt = 0;

void merge(int l, int mid, int r) {
	int p1 = l, p2 = mid + 1;
	int num = l;
	while (p1 <= mid && p2 <= r) {
		if (a[p1] < a[p2]) {
			tmp[num++] = a[p1++];
		} else {
			tmp[num++] = a[p2++];
			cnt += mid + 1 - p1;
		}
	} 
	while (p1 <= mid) {
		tmp[num++] = a[p1++];
	}
	while (p2 <= r) {
		tmp[num++] = a[p2++];
	}
	for (int i = l; i <= r; i++) {
		a[i] = tmp[i];
	}
}

void divide(int l, int r) {
	if (l < r) {
		int mid = l + (r - l) / 2;
		divide(l, mid);
		divide(mid + 1, r);
		merge(l, mid, r); 
	} 
}


int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	} 
	divide(1, n);
	cout << cnt;
	return 0;
}