描述
给定 一个序列，求其逆序对的总数。所谓逆序对是指：序列a中存在两个元素a[i]和a[j]，满足 i < j 且 a[i]>a[j]，则a[i]和a[j]为一个逆序对。
输入
第一行为正整数n（n<=100000）。
第二行有n个正整数，最大不超过1000000。
输出
输出逆序对的总数。
样例输入
5
5 2 1 3 4
样例输出
5
#include<stdio.h> long long a[100001]; long long b[100001]; long long n; long long count=0;//计数 void M(long long a[],int start,int mid,int end,long long b[])//降序 { int r=0; int pa=start; int pb=mid+1; while(pa<=mid&&pb<=end) { if(a[pa]>a[pb]) { b[r++]=a[pa++]; count=count+end-pb+1; } else { b[r++]=a[pb++]; } } while(pa<=mid) b[r++]=a[pa++]; while(pb<=end) b[r++]=a[pb++]; for(int i=0;i<end-start+1;i++) a[start+i]=b[i]; } void Msort(long long a[],int start,int end,long long b[]) { if(start<end) { int mid=start+(end-start)/2; Msort(a,start,mid,b); Msort(a,mid+1,end,b); M(a,start,mid,end,b); } } int main() { scanf("%lld",&n); for(long long i=0;i<n;i++) { scanf("%lld",&a[i]); } Msort(a,0,n-1,b); printf("%lld",count); return 0; }