HDU 1890 Robotic Sort：Splay 樹維護區間翻轉

問題描述

有一個 1..N 的排列，機器人每次將當前最小的數通過「區間翻轉」移到最前面。輸出該數翻轉前的位置（1-based）。

Splay 樹解法

利用 Splay 树（伸展树）維護序列，支持區間翻轉與刪除操作：

1. 建樹：按初始位置 1..N 建立平衡 Splay 树，每個節點記錄其值與原始索引。
2. 按值排序：將節點按值從小到大排序，依次處理。
3. 查詢位置：將目標節點 Splay 到根，其左子樹大小 + 1 即為當前位置。
4. 區間翻轉：對根的左子樹打上翻轉標記（lazy propagation）。
5. 刪除節點：將根節點刪除，並將其右子樹接為新根。

關鍵技術點

• 隱式鍵值：Splay 树不以值為鍵，而是以「中序遍歷位置」為隱式鍵，節點的 size 維護子樹大小。
• 翻轉標記：rev[x] ^= 1 交換左右孩子，下傳時遞歸翻轉。
• 雙旋優化：使用 zig-zig / zig-zag / zag-zag / zag-zig 四種雙旋操作，比單旋更高效，避免超時。
• 靜態節點池：節點內存地址固定，翻轉只改變邏輯結構，不改變節點物理位置，因此「原始索引」始終有效。

程式碼框架（核心部分）

struct Node { int ch[2], fa, sz; bool rev; } tr[MAXN];
int root, tot;

void pushup(int x) { tr[x].sz = tr[tr[x].ch[0]].sz + tr[tr[x].ch[1]].sz + 1; }
void pushrev(int x) { if (!x) return; swap(tr[x].ch[0], tr[x].ch[1]); tr[x].rev ^= 1; }
void pushdown(int x) { if (tr[x].rev) { pushrev(tr[x].ch[0]); pushrev(tr[x].ch[1]); tr[x].rev = 0; } }

bool isRoot(int x) { return tr[tr[x].fa].ch[0] != x && tr[tr[x].fa].ch[1] != x; }
void rotate(int x) { /* 單旋實現 */ }
void splay(int x, int goal) { /* 伸展操作，含 pushdown 下傳 */ }

void build(int &x, int l, int r, int fa) { /* 遞歸建平衡樹 */ }

int main() {
    int n; while (cin >> n, n) {
        // 讀入數值，記錄原始索引，按值排序
        // 建樹
        for (int i = 1; i < n; ++i) {
            splay(id[i], 0);           // 將第 i 小的數伸展到根
            pushrev(tr[root].ch[0]);   // 翻轉左子樹
            cout << tr[tr[root].ch[0]].sz + i << ' '; // 輸出位置
            // 刪除根
        }
        cout << n << '\n';
    }
}

複雜度分析

• 時間：O(N log N) 擴攤，每次操作 Splay 伸展 + 翻轉 + 刪除均為對數級。
• 空間：O(N)。

總結

本題展示了 Splay 树作為「序列維護」數據結構的強大能力：隱式鍵值 + 延遲標記 可高效支持區間翻轉、查詢排名、刪除等操作。雙旋優化是 AC 關鍵。