poj 2299 利用归并排序求逆序数

需要注意的是，逆序数的变量要设为long long。

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <algorithm>
 4 #include <string.h>
 5 #define maxn 500000+100
 6 #define _cp(a,b) ((a)<=(b))
 7 using namespace std;
 8 typedef int elem_t;
 9 int num[maxn];
10 elem_t _tmp[maxn];
11 
12 long long inv(int n,elem_t* a)
13 {
14     int l=n>>1,r=n-l,i,j;
15     long long ret=(r>1?(inv(l,a)+inv(r,a+l)):0);
16     for(i=j=0;i<=l;_tmp[i+j]=a[i],i++)
17     {
18         for(ret+=j;j<r&&(i==l||!_cp(a[i],a[l+j]));_tmp[i+j]=a[l+j],j++)
19             ;
20     }
21     memcpy(a,_tmp,sizeof(elem_t)*n);
22     return ret;
23 }
24 int main()
25 {
26     int n;
27     while(~scanf("%d",&n)&&n)
28     {
29         for(int i=0;i<n;++i)
30         {
31             scanf("%d",&num[i]);
32         }
33         printf("%lld\n",inv(n,num));
34     }
35     return 0;
36 }