首先，此題難度較高，雖說併歸排序是很前期的概念，但我個人是沒想到

於是提供另一種解題方法

此題的概念來自經典問題逆序數對

逆序數對的定義是i<j,但a[i]>a[j]

例如2,3,1裡面有(2,1),(3,1)兩組逆序數對

而氣泡排序法的基礎是若左邊比右邊大就交換

故每次交換能減少一個逆序數對

也就是說交換次數即等於逆序數對

而算逆序數對的方法

我是使用比segment tree好刻一些的"BIT"

而此題因為數字範圍很大，故還需使用"離散化"

以上的方法若完全不知道可以參考網路上的文章有非常詳細的介紹

相信可以學到很多