BZOJ 4418 [Shoi2013] 扇形面積并：二分答案 + 樹狀數組 解法詳解

題目大意

給定 n 個扇形（半徑、起始角度、結束角度），求它們覆蓋的總面積。扇形可能跨越 0°（即 l > r）。

核心思路：掃描線 + 二分答案 + BIT

1. 極坐標掃描線

• 將角度作為掃描線方向，從 -π 到 π 掃描
• 每個扇形產生兩個事件：
  進邊 (l, r, +1)、出邊 (r, r, -1)
  若 l > r（跨 0°），拆為 (l, π, +1)、(-π, r, +1) 並補一個 (-π, π, -1)？實際代碼處理：
  a[++tot] = {l, x, 1}; a[++tot] = {r, x, -1}; if (l > r) a[++tot] = {-m, x, 1};
• 按角度 p 排序所有事件

2. 面積貢獻計算

掃描到角度 θ 時，活躍扇形集合的最大半徑 R_max 決定面積微元：
dA = ½ R_max² dθ

離散化後，相鄰事件角度差 Δθ 固定，需快速查詢當前最大半徑。

3. 樹狀數組維護半徑頻次 + 二分查找最大半徑

• 半徑範圍 ≤ 281（題目約束），開 60 個 BIT（質因子數？不，代碼中 tr[61][N] 直接按半徑值維護）
• 每個半徑值一個 BIT，記錄該半徑扇形的覆蓋次數前綴和
• 查詢當前最大半徑：在 [1, maxR] 上二分，利用 BIT 查詢前綴和 > 0 判斷是否存在覆蓋

關鍵代碼片段

struct Event { int p, r, x; }; // p=角度, r=半徑, x=+1/-1
Event a[N];
int tr[61][N]; // 61個BIT，下標為半徑值

void add(int radius, int pos, int val) {
    for (int i = pos; i < N; i += i & -i) tr[radius][i] += val;
}
int query(int radius, int pos) {
    int sum = 0;
    for (int i = pos; i > 0; i -= i & -i) sum += tr[radius][i];
    return sum;
}

// 二分查找當前最大覆蓋半徑
int findMaxRadius(int l, int r) {
    int ans = 0;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (query(mid, curR) - query(mid, curL-1) > 0) {
            ans = mid; l = mid + 1;
        } else r = mid - 1;
    }
    return ans;
}

int main() {
    // 讀入、構造事件、角度離散化排序
    // 掃描線主循環
    for (int angle = -m; angle < m; ++angle) {
        // 處理該角度所有事件：add(radius, pos, x)
        int R = findMaxRadius(1, maxR);
        ans += 1LL * R * R * (angleDiff); // 面積累加
    }
}

複雜度分析

• 事件數：O(n)
• 排序：O(n log n)
• 掃描線：m 個角度位置 × (更新 BIT O(log n) + 二分查找 O(log R log n))
  總體 O(m log n log R)，m 為離散角度數

代碼中的優化細節

1. sc() 快速讀入，避免 cin 慢
2. cal(x,y) 快速冪取模（題目要求模 999911659）
3. 質因子篩選（b[300]）似乎用於其他子任務，本題未直接用到
4. BIT 二維結構 tr[61][N] 空間換時間，半徑最大 281 但開 61 可能為質因子分解優化？實際應開 maxR+1

總結

本題展示了「掃描線 + 數據結構維護極值 + 二分答案」的經典組合模式。關鍵在於將二維面積問題轉化為一維掃描線上的極值查詢，再用 BIT 支持動態增刪與前綴查詢，二分定位最大值。