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

题目：http://poj.org/problem?id=2299

这个题目实际就是求逆序数，注意 long long

上白书上的模板

 #include <iostream>

  #include<cstdio>

  #include<cstring>

  #include<cstdlib>

  #include<stack>

  #include<queue>

  #include<iomanip>

  #include<cmath>

  #include<map>

  #include<vector>

  #include<algorithm>

  using namespace std;

  long long a[],b[],sum;

  void merge_sort(long long *A, int x, int y, long long *T)

  {

      if(y-x>)

      {

          int m=x+(y-x)/; //划分

          int p=x, q=m, i=x;

          merge_sort(A,x,m,T); //递归左区间

          merge_sort(A,m,y,T);//递归右区间

          while(p<m || q<y) //有一个区间还有数的时候

          {

              if(q>=y ||(p<m && A[p] <= A[q])) //右区间没了，或者比左区间小

                  T[i++] = A[p++];   //从左区间数组复制到临时数组

              else

              {

                  T[i++] = A[q++]; //从右区间数组复制到临时数组

                  sum+=m-p;  //求逆序数，加 左边的而且比现在这个数大

              }

          }

          for(i=x; i<y; i++)

              A[i] = T[i]; //从辅助数组复制回A数组

      }

  };

  int main()

  {

      int n,i,j;

      while(cin>>n&&n)

      {

          sum=;

          for(i=; i<n; i++)

            scanf("%lld",&a[i]);

          merge_sort(a,,n,b); //一定是从0--n,刚开始n-1,调了好久

          printf("%lld\n",sum);

      }

      return ;

  }