HDU 4585 平衡樹 Treap 維護動態序列查詢第 k 大與前驅後繼

題目大意

動態維護一個數列，支持插入、查找排名、查前驅/後繼、查第 k 大。每次插入後詢問：新數與最接近它的數（差值相等取較小者）配對。

Treap 核心結構

• 節點：val, fix(隨機優先級), weight(重複計數), size(子樹大小)
• 旋裂操作：左旋、右旋維護堆序性（fix）與 BST 性質（val）
• 關鍵操作：insert, delete, find_kth, rank, pred, succ

解題邏輯

1. 插入新值 v
2. 查排名 r = rank(v)
3. 查前驅 pred = find_kth(r-1)、後繼 succ = find_kth(r+1)
4. 比較 v-pred 與 succ-v，輸出較近者（相等取 pred）

關鍵代碼片段

int rank(Node* p, int v, int cur) {
    if (!p) return 0;
    if (v == p->val) return p->left->size + cur + 1;
    if (v < p->val) return rank(p->left, v, cur);
    return rank(p->right, v, cur + p->left->size + p->weight);
}

int find_kth(Node* p, int k) {
    if (!p) return 0;
    int t = p->left->size;
    if (k <= t) return find_kth(p->left, k);
    if (k > t + p->weight) return find_kth(p->right, k - t - p->weight);
    return p->val;
}

複雜度與優勢

期望 O(log n) 各操作，比 STL 平衡樹更易控制細節（如重複值處理、排名查詢）。隨機優先級保證期望平衡。

易錯點

• 旋轉後必須更新 size
• weight 處理重複值
• 空節點 null 統一管理，避免空指針判斷