今天来水一道题目, 名字叫逆序对.

主要是复习一下归并排序的写法.

Code

#include <bits/stdc++.h>
using namespace std;
#define MAXN 500005
#define F(i, a, b) for(int i=a; i<=b;i++)
#define Fd(i, a, b) for(int i=a;i>=b;i--)
int a[MAXN], c[MAXN], n;
long long ans;
void msort(int b, int e){
	if(b==e) return;
	int mid = (b+e)/2, i=b; int j=mid+1, k=b;
	msort(b, mid); msort(mid+1, e);
	while(i<=mid && j<=e){
		if(a[i]<=a[j]) c[k++]=a[i++];
		else{
			c[k++]=a[j++];
			ans += (mid-i+1);
		}
	}
	while(i<=mid) c[k++] = a[i++];
	while(j<=e) c[k++] = a[j++];
	F(i, b, e) a[i] = c[i];
}
int main(){
	int n; cin>>n;
	F(i, 1, n) cin>>a[i];
	msort(1,n);
	cout<<ans<<endl;
}