逆序數怎麼求？很顯然有一個 的做法，從每個數字開始掃描一次，然後把逆序數對的個數加起來就行了。

如何最佳化時間複雜度？其實我們可以引入一個標記，姑且設為 ，當且僅當 被我們標記過時 。

假設我們從左到右依次掃描，某步我們掃描到 這個數字，這時我們知道：

這是我們掃描到的第 個數字；對於每個 ，只要 ，就說明這個數字 ，並且 在數列中排在 的前面，否則它一定不會在 之前被標記。也就是說，ai 和 j 構成一個“正序對”。

這時，從性質 1 和 2 可以推斷出 貢獻的逆序數大小為 （這裡假設 還沒有被標記），因為這個和式表示“正序數”， ai 和前 i-1 個數有這麼多個正序對，那麼逆序數當然就是減一下的事。

注意到這個標記的字首和，那麼顯然可以用樹狀陣列實現之。具體步驟如下：

建立樹狀陣列 ，初始化 對於每個 ，如此處理每個數字（陣列下標從 0 開始）最終結果就在 ans 裡了

就這麼簡單？對，就這麼簡單。說白了就是把一個靜態的東西（逆序數），改成一個動態的過程，把數字大小關係改造成時間維度～

其實還有一個遺留問題，如何求任意數列的逆序數，而不僅僅是 1 到 N 的排列？這個很簡單，我們只需保留數字之間的大小關係，數字本身是什麼並沒有什麼所謂，所以只需一個保序對映把數列對映成 1 到 N 的排列就行。離散化一下就行了。下面給一段示例程式碼（POJ 1804）。這個離散化不是很好，太慢了，建議用 struct。