Splay 專題復習：BZOJ 3224/1862/1503 題解與代碼

BZOJ 3224 普通平衡樹

**操作**：插入、刪除（單個）、查詢排名、查詢第 k 數、前驅、後繼。
**Splay 維護**：每節點存 son[2]、size[2]（左右子樹大小）、val、fa。旋轉時更新 size。
**重複值處理**：直接插入多個節點，用 num[l/r] 記錄子樹大小區分相同值的排名。
**前驅/後繼查詢**：找到候選節點 splay 到根，若不滿足條件則繼續在子樹中查找，直到滿足。

BZOJ 1862 GameZ 排名系統

**操作**：添加/更新玩家分數、查詢排名、查詢區間前 10 名。
**關鍵**：玩家名映射用字典樹（Trie）分配唯一 ID。Splay 關鍵字為 (score, id)，分數降序、ID 升序（先到先得）。
**區間查詢**：目標排名區間 [L, R]，中序遍歷 Splay 時只收集排名在區間內的節點，並在查詢後 splay 最近訪問節點平衡樹形。
**字符串處理**：Trie 節點 trie[node][26]，總節點數 ≤ 總字符數。

BZOJ 1503 郁悶的出納員

**操作**：I x（插入工資 x）、A x（全體 +x）、S x（全體 -x，低於最低工資離職）、F k（查詢第 k 高工資）。
**巧妙建模**：不直接修改所有節點值，維護全局增量 add。插入時存儲 val = x - add。實際值 = val + add。
**刪除低於最低工資**：插入一個 minWage - add - 1 的哨兵節點，splay 到根，其左子樹全部 < minWage，整棵左子樹刪除，統計節點數累加離職人數。
**查詢第 k 大**：利用子樹大小在 Splay 上二分下降。

核心 Splay 模板（旋轉 + Splay）

void rotate(int x, int w) { // w=0 左旋, 1 右旋
    int y = fa[x], z = fa[y];
    son[y][!w] = son[x][w];
    if (son[x][w]) fa[son[x][w]] = y;
    fa[x] = z;
    if (z) son[z][son[z][1]==y] = x;
    fa[y] = x; son[x][w] = y;
    pushup(y); pushup(x);
}
void splay(int x, int goal = 0) {
    while (fa[x] != goal) {
        int y = fa[x], z = fa[y];
        if (z != goal) {
            if ((son[y][0]==x) ^ (son[z][0]==y)) rotate(x, son[y][0]==x);
            else rotate(y, son[z][0]==y);
        }
        rotate(x, son[y][0]==x);
    }
    if (!goal) root = x;
}

總結

三道題涵蓋了 Splay 的經典應用：序列維護（平衡樹）、雙關鍵字排序（排名系統）、全局增量懶標記與子樹刪除（出納員）。關鍵在於**節點信息設計**、**旋轉時 pushup 維護**、**splay 後根節點信息即為整棵樹信息**的特性運用。