BZOJ 1861 Book 書架：Splay 維護序列操作

題目

書架初始為 1..n 排列。支持操作：
Top x：將書 x 移到最前。
Bottom x：移到最後。
Insert x y：將書 x 移到書 y 後 y>0 或前 y<0。
Ask x：查詢書 x 當前位置（1-based）。
Query k：查詢第 k 位置的書編號。
n,m ≤ 80000。

Splay 關鍵點

• 用指針數組 pos[val] 直接定位節點，O(1) 找到書 x。
• 維護子樹大小 size，支持按秩查找 (Find_kth) 和計算排名 (Rank)。
• 操作統一為：Splay 目標節點到根或指定位置，然後切割/重連子樹。
• 哨兵節點：根左右各一哨兵，簡化邊界（第 1 個實際節點排名為 2）。

核心操作

// 排名：左子樹大小 + 祖先中作右孩子時的左兄大小 + 1
int Rank(Node* x) {
    int r = x->l->sz;
    while (x != root) {
        if (x == x->p->r) r += x->p->l->sz + 1;
        x = x->p;
    }
    return r;
}

// 移動節點 x 到位置 pos (1-based, 哨兵後)
void Move(Node* x, int pos) {
    int r = Rank(x);
    // 切出 x
    Splay(Find_kth(r-1), null);
    Splay(Find_kth(r+1), root);
    root->r->l = null; pushup(root->r); pushup(root);
    // 插入到 pos
    Splay(Find_kth(pos-1), null);
    Splay(Find_kth(pos), root);
    root->r->l = x; x->p = root->r; pushup(root->r); pushup(root);
}

複雜度

均攤 O(log n)，總 O(m log n)。