Swap Linked Technique¶
介紹¶
交換是競程中常見的考題，有一些交換題目需要一些特殊技巧才可解題。
本質¶
交換題目其實在考：
相對順序的改變成本 👉 也就是交換一次時，對某條件的改變是多少。
由這個概念就可以延伸出許多變種。
逆序數對¶
逆序數對是最基本的交換，逆序數對的定義如下：
\[\text{inversion set} := S = \{(i,j) \mid i < j \wedge a_i > a_j\}\\
\text{inversion number} := n(S)\]
TODO
交換轉抽取模型¶
有些題目需要將數列 \(A\) 交換 k 次化為：
用 \(A\) 中的所有元素依序排成新的數列 \(B\)，若所需的交換次數 \(\le k\) 就是好的數列。
於是每個新增的數的交換成本就會是：此數在原數列與開頭的距離 - 1 + 中間已經被換走的數個數。
也可以記成：Position - Removed_Count。
[問題]\ 這樣寫的話，若要往後面取數字，不就不會被考慮了？
其實也會被算到！考慮一數列 1, 2, 3, 3，現在第一位已經放好 2，想要在第二位放 3：
則會需要交換 3 - 1 - 1 次，也就是 與開頭距離 (3) - 1 - 已經被換過的 2 (1) = 1 次，與預期答案相同！
題目¶
| 題目 | 詳解 |
|---|---|
| ABC227E - Swap | TODO |