d064: P-5-4. 反序數量 (APCS201806)
Tags : 分治
Accepted rate : 15人/16人 ( 94% ) [非即時]
評分方式:
Tolerant

最近更新 : 2021-02-03 10:33

Content

考慮一個數列 A[1:n]。如果 A 中兩個數字 A[i]和 A[j]滿足 $i<j$ AND $A[j]<A[i]$,

也就是在前面的比較大,則我們說(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 不超過 1e5 數列內容不超過 1e6。

Output

輸出反序對數量。

Sample Input
6
3 1 9 8 9 2
Sample Output
6
測資資訊:
記憶體限制: 64 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:
分治
出處:
AP325 [管理者:
TCIRC ($\mathbb{TCFSH}\mathtt{Computer}\mathsf{Information}\mathit{Club}$)
]


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