BZOJ 3196 / TYVJ 1730 二逼平衡樹 — 線段樹套 Treap 區間第 K 大與前驅後繼

題目功能

維護長度 n ≤ 50000 有序序列，支援 m ≤ 50000 次操作：

1. 區間 [l,r] 中 k 的排名
2. 區間 [l,r] 中排名第 k 的值
3. 單點修改 pos → k
4. 區間 [l,r] 中 k 的前驅（<k 最大值）
5. 區間 [l,r] 中 k 的後繼（>k 最小值）

資料結構選型：線段樹套 Treap

• 線段樹維護區間，每節點掛一棵 Treap（隨機平衡 BST）存該區間所有值。
• Treap 支援 O(log n) 插入、刪除、查排名、查前驅後繼。
• 單點修改 = 刪除舊值 + 插入新值，沿線段樹路徑更新 O(log n) 個 Treap。
• 區間查詢分解為 O(log n) 個線段樹節點，合併結果。

關鍵實作細節

1. Treap 節點：val, pri, cnt, size, ch[2]。pushup 維護 size。
2. 旋轉：rotate 維護堆序性。
3. 插入/刪除：遞歸插入，旋轉修正；刪除時合併左右子樹。
4. 排名查詢：rank(x) 回傳 <x 的個數。
5. 第 K 大：在線段樹上二分答案值域，利用 rank(mid) 判斷。
6. 前驅/後繼：Treap 內直接查找最大 <x / 最小 >x，線段樹合併取 max/min。

複雜度

• 建樹：O(n log² n)（每值插入 log n 層，每層 Treap 插入 log n）。
• 單次操作：O(log² n)。
• 記憶體：Treap 節點池 ≈ n log n，n=5e4 時 ~1e6 節點，~100MB 以內。

核心程式碼框架（節錄）

struct TreapNode {
    int val, pri, cnt, sz, ch[2];
} t[MAXN * 20];
int tot = 0;

void pushup(int u) { t[u].sz = t[t[u].ch[0]].sz + t[t[u].ch[1]].sz + t[u].cnt; }

void rotate(int &u, int d) { /* d=0 右旋, d=1 左旋 */ }

void insert(int &u, int x) { /* 標準 Treap 插入 */ }
void erase(int &u, int x) { /* 標準 Treap 刪除 */ }
int rank(int u, int x) { /* 返回 > 1;
    build(u<<1, l, mid); build(u<<1|1, mid+1, r);
}

void modify(int u, int pos, int oldv, int newv) {
    erase(seg[u].rt, oldv); insert(seg[u].rt, newv);
    if (seg[u].l == seg[u].r) return;
    int mid = (seg[u].l + seg[u].r) >> 1;
    if (pos <= mid) modify(u<<1, pos, oldv, newv);
    else modify(u<<1|1, pos, oldv, newv);
}

// 區間查詢示例：排名
int queryRank(int u, int L, int R, int x) {
    if (seg[u].l == L && seg[u].r == R) return rank(seg[u].rt, x);
    int mid = (seg[u].l + seg[u].r) >> 1;
    if (R <= mid) return queryRank(u<<1, L, R, x);
    if (L > mid) return queryRank(u<<1|1, L, R, x);
    return queryRank(u<<1, L, mid, x) + queryRank(u<<1|1, mid+1, R, x);
}

避坑指南

• 值域 [0, 1e8]，二分上界設 1e9。
• 操作 5 的 k 可能為負數，Treap 需支援負值。
• 記憶體池預分配避免 new 開銷；rand() 種子固定便於調試。
• 線段樹節點 4*MAXN，Treap 節點 MAXN * 20 通常足夠。