题目描述
在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。比如一个序列为4 5 1 3 2， 那么这个序列的逆序数为7，逆序对分别为(4, 1), (4, 3), (4, 2), (5, 1), (5, 3), (5, 2),(3, 2)。

输入描述: 

第一行有一个整数n(1 <= n <= 100000),  然后第二行跟着n个整数，对于第i个数a[i]，(0 <= a[i] <= 100000)。

输出描述: 

输出这个序列中的逆序数
示例1

输入 

5
4 5 1 3 2

输出 

7

思路

在归并排序的基础上稍微修改即可

代码 

//逆序数(归并排序)
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;

int n;
ll ans;//1e10
int a[N] , b[N];

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 = l;
	while(i <= mid && j <= r)
	{
		if(a[i] > a[j])
		{
			ans += mid - i + 1;
			b[k++] = a[j++];
		}
		else
			b[k++] = a[i++];
	}
	
	while(i <= mid)
		b[k++] = a[i++];
	while(j <= r)
		b[k++] = a[j++];
	
	for(int i = l ; i <= r ; i++)
		a[i] = b[i];
}

int main()
{
	scanf("%d" , &n);
	for(int i = 0 ; i < n ; i++)
		scanf("%d" , &a[i]);
	
	merge(0 , n - 1);
	printf("%lld\n" , ans);
	return 0;
}