poj 2299 求逆序数

 1 #include <iostream>
 2 const int MAX = 500000;
 3 int a[MAX];
 4 int swap[MAX];        //临时数组
 5 int n;                //数组a的长度
 6 __int64 result;            //数组a中的逆序数
 7 
 8 //归并两个已经有序的段：a[low]—a[mid]和a[mid+1]—a[high]，使得a[low]—a[high]有序。
 9 void merge(int low, int mid, int high)
10 {
11     int i = low;
12     int j = mid + 1;
13     int m = 0;
14     while(i <= mid && j <= high)
15     {
16         if(a[i] <= a[j])
17         {
18             swap[m++] = a[i];
19             i++;
20         }
21         else
22         {
23             swap[m++] = a[j];
24             j++;
25             result += mid - i + 1;
26         }
27     }
28     while(i <= mid)
29     {
30         swap[m++] = a[i];
31         i++;
32     }
33     while(j <= mid)
34     {
35         swap[m++] = a[j];
36         j++;
37     }
38     for(i = 0; i < m; i++)
39         a[low + i] = swap[i];
40 }
41 
42 //归并排序：对a[low]—a[high]进行归并排序。
43 void mergeSort(int low, int high)
44 {
45     int mid;
46     if(low < high)
47     {
48         mid = (low + high) /2;
49         mergeSort(low, mid);
50         mergeSort(mid + 1, high);
51         merge(low, mid, high);
52     }
53 }
54 
55 int main()
56 {
57     int i;
58     while(true)
59     {
60         scanf("%d",&n);
61         if(n == 0) break;
62         result = 0;
63         for(i = 0; i < n; i++)
64             scanf("%d",a+i);
65         mergeSort(0, n-1);
66         printf("%I64d
",result);
67     }
68     return 0;
69 }