逆序数（分治与归并）

在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。

如2 4 3 1中，2 1，4 3，4 1，3 1是逆序，逆序数是4。给出一个整数序列，求该序列的逆序数。

Input

第1行：N，N为序列的长度（n <= 50000) 
第2 - N + 1行：序列中的元素（0 <= Aii <= 10^9）

Output

输出逆序数

Sample Input

4
2
4
3
1

Sample Output

4

首先我们要知道归并排序是什么，如果不知道的话，不妨先看一下我的这篇博客再回来做这道题。

---->https://blog.csdn.net/doubleguy/article/details/81390951

弄懂了归并排序，那么这道题就很好做了。在归并排序的过程中，我们比较左右两端时，每当遇到当i<j&&a[i]>a[j]时那么计数器要加上mid-i+1.这里的mid-i+1是怎么来的呢？其实就是我们比较左右两端时，两端必然已经分别是有序的了，所以每当遇到i<j&&a[i]>a[j]的情况，那么这个左边i后面的所有数必然大于a[j].可以理解为mid-i+1中的1对应的是i，mid-i对应的是左端i后面的所有数。至此，代码就很好写了，无非是在归并排序的过程中增加一个计数器，满足i<j&&a[i]>a[j]的条件时，计数器增加mid-i+1就可以了。

#include<bits/stdc++.h>
using namespace std;
int ans=0;
void mergearray(int a[],int first,int mid,int last,int temp[])	//将两个有序数组合并排序 
{
	int i=first,j=mid+1;
	int m=mid,n=last;
	int k=0;
	while(i<=m&&j<=n)
	{
		if(a[i]<a[j])
			temp[k++]=a[i++];
		else
		{
			temp[k++]=a[j++];
			ans+=(mid-i+1);
		}
	}
	while(i<=m)
		temp[k++]=a[i++];
	while(j<=n)
	 	temp[k++]=a[j++];
	for(i=0;i<k;i++)
		a[first+i]=temp[i];
}

void mergesort(int a[],int first,int last,int temp[])	//将两个任意数组合并排序 
{
	if(first<last)
	{
		int mid=(first+last)/2;
		mergesort(a,first,mid,temp);	//左边有序 
		mergesort(a,mid+1,last,temp);	//右边有序 
		mergearray(a,first,mid,last,temp);	//再将两个有序数组合并 
	}
}

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