acwing788，求逆序对的数量，归并思想

#include <iostream>

using namespace std;

int n;
const int N=100005;
int  a[N],tem[N];

long long mergeSort(int a[],int l,int r){//用递归的板子解决逆序对数量 ；操作的数组，左，右 
	if(l>=r) return 0;//当区域只有一个或空时没有逆序对 
	
	long long res=0;
	int mid=l+r>>1, i=l, j=mid+1, k=0;
	res=mergeSort(a,l,mid)+mergeSort(a,mid+1,r);//先把左右区域的逆序对数量加上 
	//以下基本为归并的板子 
	while(i<=mid&&j<=r){//当i j一个达到终点时跳出 
		if(a[i]<=a[j]) tem[k++]=a[i++];
		else{
			res+=mid-i+1;
			tem[k++]=a[j++];//逆序对增加的操作，上的第一个i比j大，那么i之后的都比j大 
		}
	}
	//把另一组还未加的归并掉 
	while(i<=mid) tem[k++]=a[i++];
	while(j<=r) tem[k++]=a[j++];
	//物归原主，tem转进a 
	for(int i=l,j=0;i<=r;i++,j++) a[i]=tem[j];
	return res;
}

int main(int argc, char** argv) {
	cin>>n;
	for(int i=0;i<n;i++){
		scanf("%d",&a[i]);
	}
	cout<<mergeSort(a,0,n-1)<<endl;
	return 0;
}