HDU 5412 CRB and Queries：線段樹套笛卡爾樹解法詳解

題目背景與核心思路

HDU 5412 要求在一個數列上支持單點修改與區間第 K 小查詢。由於數值範圍較大，且操作包含修改，傳統的靜態主席樹難以直接應用。本題採用線段樹套笛卡爾樹的動態結構：先對所有出現過的數值進行離散化，建立一棵值域線段樹，每個線段樹節點維護一棵笛卡爾樹，用於記錄該值域區間內元素的下標集合。笛卡爾樹兼具二叉搜索樹與堆的性質，能以期望 O(log n) 時間完成插入、刪除與排名查詢，從而高效解決動態區間第 K 小問題。

關鍵數據結構設計

• 離散化陣列 B：收集初始數列與所有修改操作中的新值，排序去重後映射為 1..M 的整數。
• 值域線段樹：區間 [1, M]，每個節點對應一個值域範圍，存儲該範圍內所有元素下標的笛卡爾樹根節點 root[u]。
• 笛卡爾樹節點：包含 key(下標)、val(隨機優先級)、cnt(重複計數)、siz(子樹大小)、左右孩子指標。

核心操作實現

笛卡爾樹基本操作

// 旋轉操作，維持堆性質
void rotate(int &u, int d) {
    int k = nd[u].ch[d];
    nd[u].ch[d] = nd[k].ch[d^1];
    nd[k].ch[d^1] = u;
    maintain(u); maintain(k);
    u = k;
}

// 插入下標 key
void insert(int &u, int key) {
    if (u == 0) u = newNode(key);
    else if (nd[u].key == key) nd[u].cnt++;
    else {
        int d = nd[u].key < key;
        insert(nd[u].ch[d], key);
        if (nd[u].val < nd[nd[u].ch[d]].val) rotate(u, d);
    }
    maintain(u);
}

// 刪除下標 key
void erase(int &u, int key) {
    if (nd[u].key == key) {
        if (nd[u].cnt == 1) {
            if (nd[u].ch[0] == 0 && nd[u].ch[1] == 0) { u = 0; return; }
            rotate(u, nd[nd[u].ch[0]].val < nd[nd[u].ch[1]].val);
            erase(u, key);
        } else nd[u].cnt--;
    } else erase(nd[u].ch[nd[u].key < key], key);
    maintain(u);
}

// 查詢笛卡爾樹中 key <= p 的元素個數
int count(int u, int p) {
    if (u == 0) return 0;
    if (nd[u].key > p) return count(nd[u].ch[0], p);
    return nd[u].cnt + nd[nd[u].ch[0]].siz + count(nd[u].ch[1], p);
}

線段樹修改與查詢

// 線段樹單點更新：在值域位置 p 插入/刪除下標 x
void modify(int u, int l, int r, int p, int x, int v) {
    if (v > 0) insert(root[u], x);
    else erase(root[u], x);
    if (l == r) return;
    int mid = (l + r) >> 1;
    if (p <= mid) modify(lson(u), l, mid, p, x, v);
    else modify(rson(u), mid+1, r, p, x, v);
}

// 線段樹上二分查詢區間 [x, y] 第 k 小
int query(int u, int l, int r, int x, int y, int k) {
    if (l == r) return l;
    int mid = (l + r) >> 1;
    int siz = count(root[lson(u)], y) - count(root[lson(u)], x);
    if (siz >= k) return query(lson(u), l, mid, x, y, k);
    else return query(rson(u), mid+1, r, x, y, k - siz);
}

完整流程

1. 讀入初始數列 A[1..N] 並收集所有可能出現的值（包括修改操作的新值）到陣列 B。
2. 對 B 排序去重，得到離散化映射 find(x)。
3. 初始化線段樹，將初始數列每個元素 A[i] 的離散化值 find(A[i]) 及其下標 i 插入線段樹。
4. 處理 Q 個操作：
   • 修改操作：先刪除舊值對應的下標，更新 A[pos]，再插入新值對應的下標。
   • 查詢操作：在線段樹上二分，利用笛卡爾樹的 count 統計左子樹滿足條件的元素個數，決定遞歸方向，最終得到離散化值，映射回原始值輸出。

複雜度分析

• 離散化：O((N+Q) log(N+Q))
• 建樹：N 次修改，每次 O(log M * log N) 期望時間。
• 單次修改/查詢：O(log M * log N) 期望時間。
• 總體：O((N+Q) log M log N)，空間 O((N+Q) log M)。

總結

線段樹套笛卡爾樹是解決動態區間第 K 小問題的經典方案之一。笛卡爾樹隨機化特性使得代碼實現相對簡潔，且期望效能優異。本題通過離散化將數值域壓縮，結合線段樹分治值域、笛卡爾樹維護下標集合，完美應對了單點修改與區間查詢的混合操作。