PKU2299-Ultra-QuickSort

題目：http://poj.org/problem?id=2299
每組測資有至多500000個數字組成的數列，求逆序數對的對數

程式碼[作法1]：http://codepad.org/o2vDm0zg
程式碼[作法2]：http://codepad.org/SsjNylAs
需要注意逆序對的答案會超過long long
最多對的情形：假設10個數字就是9+8+7+6+5+4+3+2+1
500000就是sigma(1,499999)=124999750000

[作法1]傳統逆序數對，直接MergeSort、結束

[作法2]樹狀數組

(1)我們先考慮將原本的資料離散化
例如20,21,3,7,5，就轉化成4,5,1,3,2 (20是第四小的數給4、3是最小的數給1)
另外由於根據逆序數對的定義，遇到數字相同不算，所以必須賦予不同的值
例如3,3,3,7,9，要轉成1,2,3,4,5(也就是讓同樣的數字保持本來順序)
所以第一部分的工作就是讀入資料，並記錄原來的順序(結構陣列data)
按原值作穩定排序(見CMP)、將轉化好的數字存給ary[]

(2)利用樹狀數組
樹狀數組可以輕易地維護區間[1,n]的總和、[1,n-1]、…
所以我們定義函數sum(x)表示目前已經放了幾個介於[1,x]的數字
拿(離散好的)4,5,1,3,2來說
考慮4，目前沒有比4小的數(ans+0)，放入4
//ans += 已經放的個數-小於x數的數量 (放好的數-不用統計逆序的數 = 逆序對數)
考慮5，[1,4]有1個比5小的數(ans+0)，放入5
考慮1，目前沒有比1小的數(ans+2)，放入1
考慮3，[1,2]有1個比3小的數(ans+2)，放入3
考慮2，[1,1]有1個比2小的數(ans+3)，放入2
總答案是7，圓滿解決

(其實也可以倒著讀進來，這樣ans就是直接+=sum(x-1)的值)