POJ2299+逆序数

 /*

 归并排序+求逆序数

 */

 #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 ;

 }