UVa 11922 - Permutation Transformer

解題策略：splay tree伸展樹

splay樹

將0到n的數字加入二元樹，多出節點0是因為從1開始的區間，最左側的樹為NULL，不好處理，補上0後從1開始的區間最左側為節點0，不管怎麼分割與合併節點0都在最左側，中序走訪的第一個元素為節點0，輸出時數值0直接忽略不顯示即可。

假設輸入區間為a與b，使用splay樹進行分割與合併，利用旋轉將中序走訪第a個節點旋轉到root，再進行分割成left與tmp兩個部分，tmp再將中序走訪第b-a+1個節點旋轉到root，再進行分割成mid與right兩個部分，設定需要反轉的節點mid的屬性rev為true，旋轉與顯示前執行函式reverse檢查節點屬性rev決定是否要左右相反，並更新下一層節點的屬性rev。

最後合併left與right，再合併mid，不斷重複此動作，最後使用中序走訪就可以獲得解答。