BZOJ 1588 [HNOI2002] 營業額統計：平衡樹（Splay）維護最小波動值

問題描述

給定 n 天營業額（可為負），第一天波動值為營業額絕對值。第 i 天（i>1）波動值為當天營業額與前 i-1 天中最接近值的差的絕對值。求所有天波動值之和。

平衡樹解法

維护已出現營業額的有序集合，支持查找前驅（最大的 ≤ x）和後繼（最小的 ≥ x）。每天插入當前營業額，查詢前驅後繼取較小差值累加。Splay 或 Treap 均可，複雜度 O(n log n)。

關鍵代碼片段

inline void getpre(int k, int x) { // 查找前驅
    if (!k) return;
    if (x <= num[k]) getpre(t[k][0], x);
    else { t1 = num[k]; getpre(t[k][1], x); }
}
inline void getsuc(int k, int x) { // 查找後繼
    if (!k) return;
    if (x >= num[k]) getsuc(t[k][1], x);
    else { t2 = num[k]; getsuc(t[k][0], x); }
}

// 主循環
for (int i = 1; i <= n; ++i) {
    scanf("%d", &x);
    t1 = -INF; t2 = INF;
    getpre(rt, x); getsuc(rt, x);
    if (i != 1) ans += min(x - t1, t2 - x);
    else ans += abs(x);
    ins(rt, x, 0); // Splay 插入並伸展到根
}
printf("%d\n", ans);

注意事項

數據可能有問題，讀入需判斷 EOF。Splay 實現需正確維護旋轉、伸展操作。