這題是看樹狀數(shù)組是看到的，博客作者說這個可以用歸并排序，于是就寫了下，發(fā)現(xiàn)還好。
對于數(shù)組a,歸并排序時的合并階段，分成兩段，也就是(start,mid)和(mid,end)(我這里第一段的下標(biāo)是從start到mid-1，
第二段的下標(biāo)是從mid到end-1)。用三個下標(biāo)分別指向前面一段(i)，后面一段(j)，和新數(shù)組下標(biāo)(idx).那么當(dāng)出現(xiàn)
num[j] < num[i]的時候，結(jié)果就應(yīng)該加前面一段還沒有進(jìn)入新數(shù)組的數(shù)據(jù)的長度,比如說當(dāng)前i = 3；j = 8；mid = 5且
num[8] < num[3]；那么結(jié)果應(yīng)該加上(5-3=2)(記住我的前面一段是到mid-1結(jié)束)，因為在這次歸并的過程中要移動(5-3=2)次，
因為(num[3],num[8])是一個逆序?qū)Γ瑫r(num[4],num[8])是一個逆序?qū)?似乎這里理解起來有點困難-_-，可以畫一個圖，
自己手動執(zhí)行下，比如第一個樣例就行（9,1,0,5,4），自己手動執(zhí)行下，就知道為什么了)。那么這樣的話應(yīng)該就好做了，
最后一點就是結(jié)果會超int用long long或者_(dá)_int64存
代碼如下(依舊，建議讀者先自己寫)
CODE
1/**//*
2
ID:Klion
3 PROG:POJ_2299
4 LANG:C++
5
*/
6
#include<iostream>
7using namespace std;
8int num[500006];
9__int64 total;
10void merge(int start,int mid,int end)
11
{
12 int tmp[500006];
13 int i = start;
14 int j = mid;
15 int idx = 0;
16 //放到tmp數(shù)組里面
17 for(;i < mid && j < end;)
18
{
19 if(num[i] < num[j])
20 {
21 tmp[idx] = num[i];
22 idx++;
23 i++;
24
}
25 else
26 {
27 tmp[idx] = num[j];
28 idx++;
29 j++;
30 total += (mid-i);
31 }
32 }
33 //把剩下的都放到tmp數(shù)組里面去
34 for(;i < mid;i++)
35 {
36 tmp[idx++] = num[i];
37 }
38 for(;j < end;j++)
39 {
40 tmp[idx++] = num[j];
41 }
42 //把排好序的再賦值到num數(shù)組中
43 for(j = start,i = 0;i < idx;i++,j++)
44 num[j] = tmp[i];
45}
46void merge_sort(int start,int end)
47{
48 if(start + 1 == end)
49 {
50 return;
51 }
52 int mid = (start + end) >> 1;
53 merge_sort(start,mid);
54 merge_sort(mid,end);
55 merge(start,mid,end);
56}
57int main(void)
58{
59 freopen("2299.in","r",stdin);
60 freopen("2299.out","w",stdout);
61 int n;
62 while(scanf("%d",&n),n)
63 {
64 total = 0;
65 for(int i = 0;i < n;i++)
66 {
67 scanf("%d",&num[i]);
68 }
69 merge_sort(0,n);
70 printf("%I64d\n",total);
71 }
72 return 0;
73}
74