Input
The input contains several test cases. Every test case begins with a line that contains a single integer n < 500,000 -- the length of the input sequence. Each of the the following n lines contains a single integer 0 ≤ a[i] ≤ 999,999,999, the i-th input sequence element. Input is terminated by a sequence of length n = 0. This sequence must not be processed.Output
For every input sequence, your program prints a single line containing an integer number op, the minimum number of swap operations necessary to sort the given input sequence.Sample Input
5 9 1 0 5 4 3 1 2 3 0
Sample Output
6 0
題目大意：
給出長度為n的序列，每次只能交換相鄰的兩個元素，問至少要交換幾次才使得該序列為遞增序列。
剛剛學了時間復雜度， 用歸並排序Mergesort了，O(nlogn)，省時，不會超時。
這裡用歸並排序並不是為了求交換次數，而是為了求序列的逆序數，而一個亂序序列的逆序數 = 在只允許相鄰兩個元素交換的條件下,得到有序序列的交換次數。
案例中的
9 1 0 5 4
要把它排列為升序0，1，4，5，9
而對於序列9 1 0 5 4
9後面卻有4個比9小的元素，因此9的逆序數為4
1後面只有1個比1小的元素0，因此1的逆序數為1
0後面不存在比他小的元素，因此0的逆序數為0
5後面存在1個比他小的元素4, 因此5的逆序數為1
4是序列的最後元素，逆序數為0
因此序列9 1 0 5 4的逆序數 t=4+1+0+1+0 = 6 ，就是交換次數
（自己還不是很理解，所以拐到同學的解釋來解釋了........）
代碼如下：
1 #include <stdio.h>
2 int n,A[500005],T[500005],i;
3 long long ans=0;
4 void merge_sort(int* A,int x,int y,int*T){
5 if(y-x>1){
6 int m=x+(y-x)/2;
7 int p=x,q=m,i=x;
8 merge_sort(A,x,m,T);
9 merge_sort(A,m,y,T);
10 while(p<m||q<y){
11 if(q>=y||(p<m&&A[p]<=A[q])){
12 T[i++]=A[p++];
13 }
14 else {
15 T[i++]=A[q++];
16 ans+=m-p;
17 }
18 }
19 for(i=x;i<y;i++) A[i]=T[i];
20 }
21 }
22 int main()
23 {
24 while(scanf("%d",&n)==1&&n){
25 ans=0;
26 for(int i=0;i<n;i++)
27 scanf("%d",&A[i]);
28 merge_sort(A,0,n,T);
29 printf("%lld\n",ans);
30 }
31 return 0;
32 }
注意：保存逆序數時，必須要用long long型定義，否則會WA的。。。
