UVA 1492 Adding New Machine：線段樹掃描線解矩形覆蓋可放置區域

UVA 1492 Adding New Machine：線段樹掃描線解矩形覆蓋可放置區域

R×C 矩陣有 N 台舊機器（矩形區域），新機器 1×M，問有多少種放置位置不與舊機器重疊。M=1 時橫豎各算一次需除 2。

問題轉化

• 對每台舊機器，考慮新機器左上角放置位置。若新機器覆蓋舊機器則非法。
• 對水平放置：舊機器在行 x1..x2, 列 y1..y2。新機器左上角在 (x, y) 非法當 x ∈ [x1, x2] 且 y ∈ [y1-M+1, y2]（邊界裁剪）。
• 同理垂直放置交換 x/y 角色。
• 問題歸結為：矩形區域覆蓋後，未被覆蓋的格子數。

掃描線 + 線段樹

• 將矩形拆為「掃描線事件」：左邊 +1，右邊 -1。
• 離散化座標（列/行），構建線段樹維護覆蓋計數與未覆蓋長度。
• 掃描過程中累加 未覆蓋長度 × Δx 得總可放置面積。
• 水平+垂直兩向各算一次，M=1 時結果除 2（避免重複計算）。

關鍵數據結構

struct Segment { int l, r, h, v; }; // 掃描線段：列區間[l,r), 掃描行h, 增量v
struct Node { int l, r, h, v; }; // 線段樹節點：區間[l,r], 覆蓋計數h, 未覆蓋長度v
void pushup(int u) {
    if (node[u].h) node[u].v = bset[node[u].r+1] - bset[node[u].l];
    else if (node[u].l == node[u].r) node[u].v = 0;
    else node[u].v = node[lson].v + node[rson].v;
}

複雜度

• 事件數 O(N)，離散化坐標 O(N log N)。
• 線段樹操作 O(log N) 每事件。
• 總體 O(N log N)，N ≤ 5e4 極快。

本題是「矩形面積並」經典變體：通過離散化掃描線+線段樹維護覆蓋狀態，將二維問題降維為一維區間加減，完美解決大規模矩形覆蓋統計。