演演算法學習(22): 逆序對與原序列
逆序對與原序列
在《組合數學》中有這麼一個從逆序列構建一個排列的過程……而剛好有一場考試有考了類似的問題，於是在此總結一下。
逆序列
假定我們有序列 \(P\) 是 \(\{1, 2, \cdots, n\}\) 的一個排列。如果 \(i < j\) 並且 \(p_i > p_j\) 則稱數對 \((p_i, p_j)\) 為一個逆序對。
在逆序列中，我們令 \(r_k\) 表示 \(p_j = k\) 的逆序對數量。
注意是數值，而非下標！！！
例子：排列 \(31524\) 的逆序列為 \(1, 2, 0, 1, 0\)。
解釋：數位 \(1\) 前有一個數比他大，\(2\) 前有兩個……所以為 \(1, 2, 0, 1, 0\)。
我們不難得知：\(0 \le r_i \le n - i\)。依據乘法原理，我們可知 \(r_i\) 一共有 \(n \times (n-1) \times (n-2) \times \cdots \times 2 \times 1 = n!\) 種。
這提示我們，逆序列與排列一一對應，也就是說，唯一的逆序列可以產生唯一的排列。
那麼下面描述兩種方法通過逆序列構建一個排列。
演演算法一：相對插入法
我們令初始序列 \(P\) 為空，逆序考慮 \(k\) （\(k\ from\ n \ downto \ 1\))，重複以下步驟：
- 考慮 \(r_k\)，由於 \((k, n]\) 都已經放好，那麼可知剩下的數其實對其沒有影響。於是我們只需要將 \(k\) 放在第 \(r_k\) 個數後面即可。這樣一定可以保證 數 \(k\) 前有 \(r_k\) 個比他大的數。
在這個演演算法中，我們只做到了這些整數的相對位置不變，但是在排列中的位置是不知道的。
於是我們可以考慮下一個演演算法。
演演算法二：絕對插入法
我們先構造 \(n\) 個空位。從 \(1 \sim n\) 考慮 \(r_k\)。
- 因為 \(k\) 前面應該還有 \(r_k\) 個大於 \(k\) 的整數，而且這些數都還沒有插進來，因此，必須給這些數留出 \(r_k\) 個空位。於是我們在第 \(r_k + 1\) 的空位上放上數 \(k\)。
舉個例子：求逆序為 \(1, 2, 0, 1, 0\) 的排列。
演演算法過程也就如此。
說了兩種方法，到底哪一種可行性更高？
第一種方法利用 vector 可以很快的寫出來，但是複雜度還是近似於 \(O(n^2)\)。利用平衡樹可以把他優化到 \(O(n \log n)\) 的複雜度。
而第二種方法，不太好寫，樸素還是 \(O(n^2)\) 的複雜度。可以利用線段樹和二分做到 \(O(n \log n)\) 的複雜度，只是不太直觀。（用樹狀陣列也行，\(O(n \log^2 n)\) 但常數極小。也非常優秀）。
不過如果我們只需要求其中值的位置呢？
我們還是考慮相對插入演演算法。首先令 \(b = r_k\)，表示 \(k\) 在當前時候前面有幾個數。
那麼能夠做出貢獻的只有 \(r_i, i \in [1, k)\)。我們模仿插入的過程逆序考慮：
-
如果 \(r_i \le b\)，意味著 \(i\) 會插入到 \(k\) 前面，故令 \(b = b + 1\)。
-
否則不改變 \(b\)
最終 \(b\) 的大小也就是 \(k\) 所在的位置。
這個演演算法是 \(O(n)\) 的，也啟發我們有另外一種 \(\Theta(n^2)\) 的寫法。
再來一個問題：求某一個位置的值？
這一問題作為練習，留給讀者思考（還是考慮 \(O(n)\) 做？）
逆序個數
很多時候，出題人並不會基於這種描述方法，而是採用下標來表示。
逆序個數序列 \(b_i\) 表示 \(\sum_{j < i}[p_j > p_i]\)，也就是第 \(i\) 個數前有幾個數比它大。
我們可以稍加改變前文中的兩個演演算法，從而得到求逆序的一種方法。
這裡講一下基於相對插入法的做法吧。
相對插入法
還是類似的，令初始序列為空，從前向後考慮下表 \(i\)：
-
我們將 \(i\) 放在從後向前 \(b_i\) 個數前（若 \(b_i = 0\)，則直接放在末端）
注意，是直接放下標
於是最終序列 \(a_i = rank(i)\)，也就是 \(i\) 從前向後數的位置。
那麼這裡考慮某一個位置的值？
我們從前向後考慮，令 \(r\) 表示在序列中 \(i\) 後面的數的個數，考慮什麼時候 \(b_j\) 會對 \(r\) 做出貢獻？若 \(b_j \le r\)，那麼意味著 \(j\) 會放在 \(i\) 的右側，那麼此時令 \(r = r + 1\)。
於是最終 \(a_i = n - r\)。
於是我們有了 \(\Theta(n^2)\) 的做法了……
帶修改問題
考慮這樣一個問題：對於逆序對序列 \(b_i\)，要求支援單點修改 \(b_i\)，以及單點查詢 \(a_i\)。
原題為 CF1540D
這道題需要用到分塊。
考慮以下事實：
-
對於一定的序列 \(b_i\)，如果初始值為 \(r\)，則經過操作後 \(r \to r'\) 的結果是一定的。這啟發我們可以分塊。
-
而考慮對於每一個 \(r \in [1, n]\)，對應的結果 \(r'\) 一定是不下降的。也就是說我們令 \(f(r)\) 表示 \(r\) 經過了序列之後變成的值，\(f\) 是一個不嚴格單調上升序列。
於是對於每一塊，考慮用線段樹維護（支援區間加和二分求某個值的位置），初始 \(T_i= i\)。
在加入 \(b_j\) 是，考慮先找到所有 \(\ge b_j\) 的 \(T_i\) ，並整體加 \(1\)。不難發現，其實每一次只是字尾 \(+1\)，而原序列的單調的，所以新的序列是單調，這為線段樹上二分查詢提供了充分的條件。（其實還是可以用二分的樹狀陣列，只是複雜度為 \(O(B \log^2 n)\)，還是常數很小）
於是我們可以在 \(O(B \log n)\) 的複雜度中處理出函數 \(f\)，並可以在 \(O(\log n)\) 內找到對應的值。於是查詢的複雜度為 \(O(\frac nB \log n)\)。
考慮修改？暴力重構每一塊就是了。修改為 \(O(B \log n)\)。
塊長設為 \(\sqrt n\) 即可，總複雜度為 \(O(n \sqrt n \log n)\)，講道理是可以過的。