POJ2299 UltraQuickSort

　　归并排序求逆序数，nlog(n)，500多ms。答案最大可以达到n * (n + 1) / 2，要开long long。

View Code

 1  #include <stdio.h>
 2  #include <stdlib.h>
 3  #define N 500005
 4  #define LL __int64
 5  LL a[N], b[N];
 6  int n;
 7  
 8  LL cal(LL s, LL t)
 9  {
10      LL i, j, k, mid;
11      LL res;
12      if(t - s == 1)
13          return 0;
14      mid = (s + t) >> 1;
15      res = cal(s, mid) + cal(mid, t);
16      i = s, j = mid, k = s;
17      while(i < mid && j < t)
18      {
19          if(a[i] <= a[j])
20              b[k ++] = a[i ++], res += j - mid;
21          else
22              b[k ++] = a[j ++];
23      }
24      while(i < mid) b[k ++] = a[i ++], res += j - mid;
25      while(j < t) b[k ++] = a[j ++];
26      for(i = 0; i < t - s; i ++)
27          a[s + i]= b[s + i];
28      return res;
29  }
30  
31  int main()
32  {
33      while(scanf("%d", &n), n)
34      {
35          for(LL i = 0; i < n; i ++)
36              scanf("%I64d", &a[i]);
37          printf("%I64d\n", cal(0, n));
38      }
39      return 0;
40  }

　　POJ1007用的是一样的算法。