這題用樹狀數(shù)組比歸并排序快很多啊~~~
一個是500多一個2000多。
這題用樹狀數(shù)組，主要有兩點(diǎn)
I.離散化，把n個數(shù)映射到1-n里面，不然內(nèi)存不夠，
II.求一個數(shù)組的某一個數(shù)據(jù)的前面所有數(shù)據(jù)中比它小(或大)的所有數(shù)的個數(shù)
對于第一個，我們可以用一個struct，然后里面存兩個信息，一個是val，一個是no，其中val是輸入的數(shù)，no是用來離散化的。
對于第二個，很多人說是樹狀數(shù)組的基本功了，但是我覺得看怎么結(jié)束樹狀數(shù)組的。在這里你可以對每一個數(shù)update(a[i],1),然后再getsum(a[i])(a[i]是離散化后的數(shù)組)。這樣的話，你再用i - getsum(a[i])就是逆序數(shù)的對數(shù)了，如果不好理解的話，可以用5 2 1 4 3這個數(shù)組來模擬下。
對于這兩個問題解決了之后，這題就簡單了
下面給出代碼(還是建議自己先想，不過離散化沒接觸的，可能會比較難想，樹狀數(shù)組還行吧)

CODE