POJ2299+逆序数

归并排序！！！！！！！！！！
 1 /*
 2 归并排序+求逆序数
 3 */
 4 #include<stdio.h>
 5 #include<string.h>
 6 #include<algorithm>
 7 #include<stdlib.h>
 8 using namespace std;
 9 typedef __int64 int64;
10 const int maxn = 500005;
11 int64 a[ maxn ],Sort[ maxn ];
12 int64 res;
13 
14 void init(){
15     res = 0;
16 }
17 
18 void merge( int L,int R ){
19     int mid = (L+R)/2;
20     int i = L;
21     int j = mid+1;
22     int pos = L;
23     while( i<=mid&&j<=R ){
24         if( a[i]<a[j] )
25             Sort[ pos++ ] = a[i++];
26         else{
27             Sort[ pos++ ] = a[j++];
28             res += (mid-i+1);
29         }
30     }
31     while( i<=mid )
32         Sort[ pos++ ] = a[i++];
33     while( j<=R )
34         Sort[ pos++ ] =  a[j++];
35     for( int k=L;k<=R;k++ )
36         a[k] = Sort[k];
37 }
38 
39 void merge_sort( int L,int R ){
40     int mid = (L+R)/2;
41     if( L<R ){
42         merge_sort( L,mid );
43         merge_sort( mid+1,R );
44         merge( L,R );
45     }
46     return ;
47 }
48 
49 int main(){
50     int n;
51     while( scanf("%d",&n),n ){
52         for( int i=1;i<=n;i++ )
53             scanf("%I64d",&a[i]);
54         init();
55         merge_sort( 1,n );
56         printf("%I64d
",res);
57     }
58     return 0;
59 }
View Code
keep moving...