Colourful Rectangle：三原色疊加的區間面積並問題

Colourful Rectangle：三原色疊加的區間面積並問題

平面上有 N 個矩形，每個矩形顏色為 R、G、B 三原色之一。顏色疊加規則：R+G=Y，R+B=M，G+B=C，R+G+B=W。求每種顏色（R,G,B,Y,M,C,W）最終覆蓋的總面積。

掃描線 + 線段樹維護顏色狀態

• 將矩形邊拆為水平掃描線事件：下邊 +顏色，上邊 -顏色。
• X 座標離散化，構建線段樹維護每個 X 區間的顏色覆蓋狀態。
• 線段樹節點記錄：cnt[3] 三原色覆蓋計數；len[8] 8 種顏色（0..7 對應二進制組合）在該區間的長度。
• 維護邏輯：若某原色計數 >0，則該區間被該原色完全覆蓋，子區間的其他顏色被「蓋住」合成新顏色。

關鍵維護函數

void maintain(int v) {
    int sta = 0;
    for (int i = 0; i < 3; ++i) if (tree[v].cnt[i] > 0) sta |= (1 << i);
    if (sta) {
        memset(tree[v].len, 0, sizeof(tree[v].len));
        tree[v].len[sta] = X[tree[v].r+1] - X[tree[v].l];
        if (tree[v].l != tree[v].r) {
            for (int i = 1; i < 8; ++i) {
                if ((sta | i) != sta) { // 子區間有 sta 沒有的顏色
                    int mixed = sta | i;
                    int subLen = tree[v*2].len[i] + tree[v*2+1].len[i];
                    tree[v].len[mixed] += subLen;
                    tree[v].len[sta] -= subLen;
                }
            }
        }
    } else if (tree[v].l == tree[v].r) {
        memset(tree[v].len, 0, sizeof(tree[v].len));
    } else {
        for (int i = 1; i < 8; ++i)
            tree[v].len[i] = tree[v*2].len[i] + tree[v*2+1].len[i];
    }
}

完整流程

1. 讀入矩形，生成事件（x1, x2, y, color, +1/-1），收集 X 座標離散化。
2. 事件按 y 排序，掃描線處理：更新線段樹，累加 area[color] += len[color] * (nextY - curY)。
3. 輸出 7 種顏色面積（順序：R, G, B, Y, M, C, W）。

複雜度

• 離散化：O(N log N)
• 掃描線：O(N log N) 事件處理，每次更新 O(log N)
• 總時間：O(N log N)，空間：O(N)

總結

經典的「矩形面積並」變體，引入三原色疊加語義。關鍵在於線段樹節點維護「三原色覆蓋計數」而非單一顏色，並通過位掩碼合成 8 種顏色長度。維護邏輯需仔細處理「父節點有顏色時子節點顏色被合成」的情況。