BZOJ 1227 [SDOI2009] 虔誠的墓主人：離線處理 + 樹狀數組 + 離散化的極致應用

問題大意

在 10⁹ × 10⁹ 的巨大網格中給出最多 10⁵ 棵樹，每棵樹有坐標 (x, y) 和權值。需計算滿足特定幾何條件的四元組數量，答案模 2³¹。暴力枚舉不可行，必須採用離線算法。

核心思路：掃描線 + 樹狀數組

1. 座標離散化

網格過大但點少，將 y 座標離散化映射到 [1, tot]，僅保留有樹的列，空間從 10⁹ 降為 10⁵。

2. 排序與掃描順序

所有點按 x 降序，x 同則 y 降序 排序。從右上向左下掃描，模擬「將點加入左側/上側集合」的過程。

3. 樹狀數組維護的值

對於離散化後的列 i，維護：

• u[i]：當前掃描線左側（x 更大）該列的樹數
• d[i]：當前掃描線右側（x 更小）該列的樹數
• 樹狀數組存儲 C(u[i], K) × C(d[i], K) 的前綴和

其中 C(n, k) 為組合數，預處理所有 n ≤ 10⁵ 的值。

4. 動態更新與查詢

掃描到新點 (x, y) 時：

• 若換行（x 變化），重置左右計數器 l, r。
• 查詢區間 (y_prev, y_cur) 的組合數和，乘以 C(l, K) × C(r, K) 累加到答案。
• 更新該列狀態：u[y]--, d[y]++，並更新樹狀數組差值。

關鍵代碼結構

// 初始化組合數
void init() {
    c[0][0] = 1;
    for (int i = 1; i <= w; i++) {
        c[i][0] = 1;
        for (int j = 1; j <= min(i, K); j++)
            c[i][j] = (c[i-1][j] + c[i-1][j-1]) % mod;
    }
}

// 掃描主循環
for (int i = 1; i <= w; i++) {
    if (a[i].x != tmp_line) { // 換行
        // 重置 l, r
        // 更新當前點列狀態
    } else { // 同行
        // 查詢區間和
        // 累加答案
        // 更新當前點列狀態
    }
}

複雜度分析

• 離散化排序：O(w log w)
• 組合數預處理：O(w × K)
• 掃描過程：每點一次樹狀數組查詢/更新 O(log w)，總計 O(w log w)
• 總體 O(w log w + wK)，完美應對 w ≤ 10⁵。

總結

本題是離線掃描線、樹狀數組動態維護、組合數學與離散化綜合應用的經典範例。將二維幾何問題轉化為一維序列問題，再用數據結構高效維護區間統計，展現了算法設計的層層遞進之美。