## 逆序數對

???+note "[TIOJ 1080 逆序數對](https://tioj.ck.tp.edu.tw/problems/1080)"
	給定一個序列 $A=(a_1, a_2, \ldots, a_n)$。我們說一個逆序數對是 $i < j$ 且 $a_i > a_j$，算出這個序列有幾個逆敘數對

### 解法 1 - 分治

- merge sort

### 解法 2 - 值域分治

- 假設**中位數**[^1]為 $\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)$ 

!!! question "輸入有很多相同的數字時，按照數值做分治法會不會有什麼問題 ?"
	因為是中位數，每次數字種類會減少一半，遞迴到只剩一種數字即可停止，所以其實沒有影響
	
	注意如果 $\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` 函式