POJ2299+逆序数

时间:2021-08-14 15:15:43

归并排序!!!!!!!!!!

 /*
归并排序+求逆序数
*/
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<stdlib.h>
using namespace std;
typedef __int64 int64;
const int maxn = ;
int64 a[ maxn ],Sort[ maxn ];
int64 res; void init(){
res = ;
} void merge( int L,int R ){
int mid = (L+R)/;
int i = L;
int j = mid+;
int pos = L;
while( i<=mid&&j<=R ){
if( a[i]<a[j] )
Sort[ pos++ ] = a[i++];
else{
Sort[ pos++ ] = a[j++];
res += (mid-i+);
}
}
while( i<=mid )
Sort[ pos++ ] = a[i++];
while( j<=R )
Sort[ pos++ ] = a[j++];
for( int k=L;k<=R;k++ )
a[k] = Sort[k];
} void merge_sort( int L,int R ){
int mid = (L+R)/;
if( L<R ){
merge_sort( L,mid );
merge_sort( mid+,R );
merge( L,R );
}
return ;
} int main(){
int n;
while( scanf("%d",&n),n ){
for( int i=;i<=n;i++ )
scanf("%I64d",&a[i]);
init();
merge_sort( ,n );
printf("%I64d\n",res);
}
return ;
}