基礎技巧

逆序數對

TIOJ 1080 逆序數對

給定一個序列 \(A=(a_1, a_2, \ldots, a_n)\)。我們說一個逆序數對是 \(i < j\) 且 \(a_i > a_j\)，算出這個序列有幾個逆敘數對

解法 1 - 分治

• merge sort

解法 2 - 值域分治

• 假設中位數¹為 \(\text{mid}\)

• 準備一個新的陣列 \(b\)，\(a\) 陣列中大於 \(\text{mid}\) 的設為 \(1\)，其他設為 \(0\)

• 對於 \(b\) 內的每個 \(0\)，計算計算前方有幾個 \(1\)

\[\begin{array}{|c|c|c|c|c|c|c|c|c|} \hline a & 6 & 3 & 1 & 7 & 5 & 8 & 2 & 4 \\\\ \hline b & 1 & 0 & 0 & 1 & 1 & 1 & 0 & 0 \\\\ \hline \end{array}\]

• 複雜度 : \(O(n\log n)\)

輸入有很多相同的數字時，按照數值做分治法會不會有什麼問題 ?

因為是中位數，每次數字種類會減少一半，遞迴到只剩一種數字即可停止，所以其實沒有影響

注意如果 \(\begin{align}\text{mid} = \frac{l+r}{2}\end{align}\) 數值分布不會均衡

解法 3 - 資料結構

• BIT

解法 4 - 掃描線

• 把輸入想成 \(n\) 個平面上的點,第 \(i\) 個點座標為 \((i, a_i)\)
• 逆序數對個數即為 : 每個點的右下角點數總和

Implace Merge

將一個陣列中的兩個有序數列區間 [l, mid), [mid, r) 合併成一個有序數列

Karasuba

---

1. 找中位數用 nth_element 函式 ↩