http://poj.org/problem?id=2299
题目就是让用归并排序求逆序数的。逆序数简单定义为：当i<j 时有Ai>Aj 则（Ai Aj） 就是一对逆序数
1 #include<stdio.h>
2 #include<string.h>
3 #include<iostream>
4 using namespace std;
5 #define N 500001
6 __int64 sum;
7 int a[N],b[N];
8 void merg(int l,int mid,int r)
9 {
10 int i;
11 int p=l,q=mid+1,s=l;
12 while((p<=mid)&&(q<=r))
13 {
14 if(a[p]<a[q])
15 b[s++]=a[p++];
16 else {b[s++]=a[q++]; sum+=mid-p+1;}
17 }
18 while(p<=mid) b[s++]=a[p++];
19 while(q<=r) b[s++]=a[q++];
20 for(i=l;i<=r;i++)
21 a[i]=b[i];
22 }
23 void mergsort(int l,int r)
24 {
25 int mid=(l+r)/2;
26 if(l<r)
27 {
28 mergsort(l,mid);
29 mergsort(mid+1,r);
30 merg(l,mid,r);
31 }
32 }
33 int main()
34 {
35 int i,n;
36 while(cin>>n,n)
37 {
38 sum=0;
39 for(i=0;i<n;i++)
40 cin>>a[i];
41 mergsort(0,n-1);
42 printf("%I64d\n",sum);
43 }
44 return 0;
45 }