UVA 1493 Draw a Mess：並查集優化矩形覆蓋面積統計

UVA 1493 Draw a Mess：並查集優化矩形覆蓋面積統計

矩形區域內四種繪圖指令（圓、菱形、三角形、矩形），後繪蓋前。最終統計 9 種顏色各佔面積。N, M ≤ 200×50000，Q ≤ 50000。

核心技巧：逆序處理 + 並查集跳過已染色

• 將指令反序處理：先處理最後一條指令，其覆蓋區域確定最終顏色。
• 對每行維護並查集 f[row][col]，指向下一個未染色列。染色後 f[row][col] = col+1，路徑壓縮實現 O(α) 查找下一可染色位置。
• 各形狀逐行計算覆蓋列區間 [star, end]，在區間內用並查集跳躍染色並計數。

形狀覆蓋行區間計算

• 圓/菱形/三角形：對行 i，半寬 R = get_R(r, x, i, sign)，列區間 [max(y-R,0), min(y+R, M-1)]。
• 矩形：行區間 [x, x+r-1]，列區間 [y, y+w-1]。

關鍵代碼

int count(int x, int y, int r, int star, int end, int sign) {
    int ret = 0;
    for (int i = star; i <= end; i++) {
        int R = get_R(r, x, i, sign);
        int mv = max(y - R, 0);
        while ((mv = getfar(f[i], mv)), abs(mv - y) <= R && mv < M) {
            ret++; f[i][mv] = mv + 1;
        }
    }
    return ret;
}

複雜度

• 每個格子最多被染色一次，並查集操作均攤 O(α)。
• 總時間 O(N*M*α) ≈ 1e7，空間 O(N*M) ≈ 1e7 int，可行。

本題是「逆序離線+並查集跳過」技巧的教科書級應用，將二維區域覆蓋問題降維為逐行區間染色，完美解決大規模覆蓋統計。