poj 2299 Ultra-QuickSort (归并排序 求逆序数)

 1 #include <iostream>
 2  #include<cstdio>
 3  #include<cstring>
 4  #include<cstdlib>
 5  #include<stack>
 6  #include<queue>
 7  #include<iomanip>
 8  #include<cmath>
 9  #include<map>
10  #include<vector>
11  #include<algorithm>
12  using namespace std;
13  
14  long long a[600000],b[500000],sum;
15  void merge_sort(long long *A, int x, int y, long long *T)
16  {
17      if(y-x>1)
18      {
19          int m=x+(y-x)/2; //划分
20          int p=x, q=m, i=x;
21          merge_sort(A,x,m,T); //递归左区间
22          merge_sort(A,m,y,T);//递归右区间
23          while(p<m || q<y) //有一个区间还有数的时候
24          {
25              if(q>=y ||(p<m && A[p] <= A[q])) //右区间没了，或者比左区间小
26                  T[i++] = A[p++];   //从左区间数组复制到临时数组
27              else
28              {
29                  T[i++] = A[q++]; //从右区间数组复制到临时数组
30                  sum+=m-p;  //求逆序数，加 左边的而且比现在这个数大
31              }
32  
33          }
34          for(i=x; i<y; i++)
35              A[i] = T[i]; //从辅助数组复制回A数组
36      }
37  };
38  int main()
39  {
40      int n,i,j;
41      while(cin>>n&&n)
42      {
43          sum=0;
44          for(i=0; i<n; i++)
45            scanf("%lld",&a[i]);
46          merge_sort(a,0,n,b); //一定是从0--n,刚开始n-1,调了好久
47          printf("%lld
",sum);
48      }
49      return 0;
50  }
51