788. 逆序对的数量

link

code

#include<bits/stdc++.h>

using namespace std;

const int N = 100010;

int a[N];
int tp[N];
long long ans;

void merge(int l, int r){
	if(l >= r) return;
	int mid = l + r >> 1;
	merge(l ,mid), merge(mid + 1, r);
	int i = l, j = mid + 1, k = 0;
	while(i <= mid && j <= r){
		if(a[i] <= a[j]){
			tp[k++] = a[i++];
		}else{
			tp[k++] = a[j++];
			ans += mid - i + 1;
		}
	}
	while(i <= mid) tp[k++] = a[i++];
	while(j <= r)   tp[k++] = a[j++];
	
	for(int i = 0; i < k; i++)
	a[i + l] = tp[i];
}

int main(){
	int n; cin >> n;
	for(int i = 1; i<= n; i++) cin >>a[i];
	merge(1,n);

	cout << ans;
	return 0;
}