BZOJ 1208 [HNOI2004] 寵物收養所：Splay 树動態維護最小絕對差值

問題建模

收養所同時只存在「待領養寵物」或「等待領養者」，不會共存。每次操作：

• 寵物到達（a=0, 值=b）：若有等待者，匹配特點值最接近的領養者（差值相同取較小值），累加不滿意度 |a-b|；否則寵物入庫
• 領養者到達（a=1, 值=b）：若有寵物，匹配最接近寵物（同規則），累加不滿意度；否則領養者入庫

最終輸出總不滿意度模 1,000,000。n ≤ 80,000，同類實體同時在庫 ≤ 10,000。

核心洞察：平衡樹維護單側集合

由於收養所內「非寵物即領養者」，可用一棵平衡樹（Splay/Treap/紅黑樹）維護當前在庫實體的特點值，並用一個標記 flag 區分當前樹中存的是寵物（0）還是領養者（1）。

• 新來實體類型 == flag：直接插入樹中
• 新來實體類型 != flag：在樹中查找前驅（最大的 ≤ x）和後繼（最小的 ≥ x），取差值較小者（相同取前驅），刪除該節點，累加差值

Splay 關鍵操作實現

// 節點結構
struct Node {
    int ch[2], fa, size;
    long long val;
    int rnd; // Treap 優先級，或用 Splay 的旋轉邏輯
} t[MAXN];

// 查找前驱：最大的 < x
long long pre(int k, long long x) {
    if (!k) return -INF;
    if (x <= t[k].val) return pre(t[k].ch[0], x);
    long long tmp = pre(t[k].ch[1], x);
    return tmp == -INF ? t[k].val : tmp;
}

// 查找後繼：最小的 > x
long long suc(int k, long long x) {
    if (!k) return INF;
    if (x >= t[k].val) return suc(t[k].ch[1], x);
    long long tmp = suc(t[k].ch[0], x);
    return tmp == INF ? t[k].val : tmp;
}

// 刪除節點（標準 Splay 刪除：旋伸到根，接上左右子樹）
void del(int &k, long long x) { ... }

完整邏輯流程

long long ans = 0;
int flag = -1; // -1 空，0 寵物，1 領養者
int root = 0;

for (int i = 1; i <= n; ++i) {
    int type; long long val;
    read(type, val);
    
    if (root == 0 || type == flag) { // 樹空或同類
        flag = type;
        insert(root, val);
    } else { // 異類：匹配並刪除
        long long p = pre(root, val);
        long long s = suc(root, val);
        long long diff;
        if (val - p <= s - val) { // 相等取前驱（較小值）
            diff = val - p;
            del(root, p);
        } else {
            diff = s - val;
            del(root, s);
        }
        ans = (ans + diff) % 1000000;
        if (root == 0) flag = -1; // 樹空重置標記
    }
}
printf("%lld\n", ans);

關鍵細節與避坑指南

• 取模時機：題目要求最終結果模 1,000,000，但中間過程建議每次累加後取模，防止 long long 溢出（雖 80,000 × 2^31 < 2^63）
• 前驱/後繼邊界：定義 INF = 1e18，前驅不存在返回 -INF，後繼不存在返回 INF，比較差值時自動排除
• 相等差值取較小值：條件 val - p <= s - val 確保差值相等時選前驅（對應題目「a-b 優先」）
• 輸入讀取優化：大數據量下需用快速讀（getchar() 解析）避免 TLE

複雜度分析

• 每次操作：O(log K)，K 為當前樹中節點數（≤10,000）
• 總時間：O(n log K) ≈ 80,000 × 14 ≪ 1s
• 空間：O(K) ≤ 10,000 節點

總結

本題展示了「單側集合動態匹配」的經典模型：用一棵平衡樹維護當前未匹配實體，新來異類實體查前驱後繼即得最優匹配。Splay 代碼量較大，實戰中可用 std::set（紅黑樹）極簡實現：

set s;
auto it = s.lower_bound(val); // 後繼
long long suc = (it == s.end()) ? INF : *it;
long long pre = (it == s.begin()) ? -INF : *prev(it);
// ... 比較差值、刪除、累加 ...
// s.erase(matched_val);

std::set 版本代碼量減少 80%，常數略大但完全通過時限，工程實踐首選。