d064. P_5_4 反序數量 (APCS201806)

Content

考慮一個數列 $A[1:n]$ 。如果 $A$ 中兩個數字 $A[i]$ 和 $A[j]$ 滿足 $i<j$ 且 $A[i]>A[j]$，也就是在前面的比較大，則我們說 $(A[i],A[j])$ 是一個反序對(inversion)。定義 $W(A)$ 為數列 $A$ 中反序對數量。

例如，在數列 $A=(3,1,9,8,9,2)$ 中，一共有 $(3,1)、(3,2)、(9,8)、(9,2)、(8,2)、(9,2)$ 一共 $6$ 個反序對，所以 $W(A)=6$。

請注意到序列中有兩個 $9$ 都在 $2$ 之前，因此有兩個 $(9,2)$ 反序對，也就是說，不同位置的反序對都要計算，不管兩對的內容是否一樣。請撰寫一個程式，計算一個數列 $A$ 的反序數量 $W(A)$ 。

Input

第一行是一個正整數 $n$，代表數列長度，

第二行有 $n$ 個非負整數，是依序數列內容，數字間以空白隔開。 $n$ 不超過 $10^5$ ，數列內容不超過 $10^6$ 。

Output

輸出反序對數量。

Sample Input #1

6
3 1 9 8 9 2

Sample Output #1

Sample Input #2

5
7 7 5 2 1

Sample Output #2

測資資訊：

記憶體限制： 256 MB
公開測資點#0 (20%): 1.0s , <1M
公開測資點#1 (20%): 1.0s , <1M
公開測資點#2 (20%): 1.0s , <1M
公開測資點#3 (20%): 1.0s , <1M
公開測資點#4 (20%): 1.0s , <1M

Hint ：

Tags:

ch5

出處:

Prof. Wu [管理者：

ktlai (K．我已霸榜．Tlai)

]

ID	User	Problem	Subject	Hit	Post Date
沒有發現任何「解題報告」