a132. 逆序數對 - 旦旦解題農場

內容

給定一個數列$A$，求有多少個數對$i,j$滿足$i\lt j , A_i\gt A_j$。

輸入說明

第一行有一個正整數$T$，接下來有$T$筆測資。

每筆測資第一行有一個正整數$n$，第二行有$n$個正整數$A_i$。

20%測資$n\le 1000$

60%測資$n\le 10^5$

100%測資$n\le 10^6$

所有測資$T\le 5,A_i\le 10^9$

輸出說明

求陣列$A$有幾組逆序數對。

範例輸入

範例輸出

5
4

測資資訊：

記憶體限制： 64 MB
公開測資點#0 (10%): 1.0s , <1M
公開測資點#1 (10%): 1.0s , <1M
公開測資點#2 (10%): 1.0s , <10M
公開測資點#3 (10%): 1.0s , <10M
公開測資點#4 (10%): 1.0s , <10M
公開測資點#5 (10%): 1.0s , <10M
公開測資點#6 (10%): 1.0s , <50M
公開測資點#7 (10%): 1.0s , <50M
公開測資點#8 (10%): 1.0s , <50M
公開測資點#9 (10%): 1.0s , <50M

提示：

合併的時候，其實計算答案與合併排序可以同時做，而不用分開跑兩次，如果你的作法是後者，你有可能最後一筆測資會TLE。

標籤:

出處:

[管理者：

giver (垃圾)

]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」