題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 🟡 ABC434D Clouds

Problem Statement

題目簡述

在一個 2000×20002000 \times 2000 的網格中有 NN 朵雲，每朵雲覆蓋一個矩形區域 (Ui,Di)(U_i, D_i) 列以及 (Li,Ri)(L_i, R_i) 行。
對於每一朵雲，求若「僅移除這朵雲」後，網格中完全沒被任何雲覆蓋的格子總數。

Constraints

約束條件

  • 1≤N≤2×1051 \le N \le 2 \times 10^5
  • 1≤Ui≤Di≤20001 \le U_i \le D_i \le 2000
  • 1≤Li≤Ri≤20001 \le L_i \le R_i \le 2000

思路：二維差分與二維前綴和

這是一道涉及二維空間覆蓋計數的經典題型。由於網格大小僅有 2000×20002000 \times 2000，我們可以承受 O(HW)\mathcal{O}(HW) 的時間與空間複雜度。

1. 問題分析

如果不移除任何雲，我們可以算出目前網格的覆蓋狀況。當我們試圖移除第 kk 朵雲時：

  • 如果某個被第 kk 朵雲覆蓋的格子，同時也被其他雲覆蓋（即覆蓋次數 ≥2\ge 2），那移除雲 kk 後，這個格子依然有雲遮蔽。
  • 如果某個格子只被第 kk 朵雲覆蓋（即覆蓋次數 =1= 1），那麼移除雲 kk 後，這個格子就會變成無雲遮蔽的狀態。

因此，對於每一朵雲，移除它後真正增加的「無雲遮蔽格子數」，就是這朵雲覆蓋範圍內「恰好被覆蓋一次的格子數」。

核心轉換

移除雲 kk 後的空白格子總數 = （原先本來就不在任何雲底下的空白格子數）+（雲 kk 範圍內，恰被覆蓋 1 次的格子數）

2. 實作步驟

要高效查詢任意矩形區域內「恰好覆蓋 11 次」的格子數，我們需要進行前置處理：

  1. 二維差分計算覆蓋次數
    • 由於有 NN 次區間覆蓋操作，暴力覆蓋會導致超時。
    • 利用二維差分（2D Difference Array），可以在 O(1)\mathcal{O}(1) 時間內標記矩形區間的加減操作。
    • 遍歷完所有雲的範圍之後，對差分陣列做一次二維前綴和，即可計算出每個格子真實的被覆蓋次數。
  2. 統計初始空白格子數
    • 掃描還原後的覆蓋次數網格，計算覆蓋次數為 00 的格子總數，將此數值標記為基準的空白格子數並記錄下來。
  3. 對覆蓋次數為 1 的格子做二維前綴和快速查詢
    • 建立一個新的標記網格，記錄每個格子是不是「恰被覆蓋 11 次」（若是則標記為 11，否則為 00）。
    • 對這份由 00 和 11 構成的標記網格進行二維前綴和（2D Prefix Sum）。
  4. 計算答案
    • 對於每一朵雲，利用已經建立好的前綴和標記網格，可以在 O(1)\mathcal{O}(1) 的時間內算出其原始覆蓋範圍內包含的「恰被覆蓋 11 次格子總和」。
    • 將該總和加上最初記錄的基準空白格子數，即為移除這朵雲後，網格中真正的空白格子總數。

複雜度分析

  • 時間複雜度：O(HW+N)\mathcal{O}(HW + N)
  • 空間複雜度：O(HW)\mathcal{O}(HW)。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
H = W = 2000


def solve():
    N = int(input())
    clouds = [tuple(map(int, input().split())) for _ in range(N)]

    # 二維差分維護每個格子被覆蓋的次數
    grid1 = [[0] * (W + 2) for _ in range(H + 2)]
    for x1, x2, y1, y2 in clouds:
        grid1[x1][y1] += 1
        grid1[x2 + 1][y2 + 1] += 1
        grid1[x1][y2 + 1] -= 1
        grid1[x2 + 1][y1] -= 1
    for i in range(1, H + 2):
        for j in range(1, W + 2):
            grid1[i][j] += grid1[i - 1][j] + grid1[i][j - 1] - grid1[i - 1][j - 1]

    tot0 = 0
    for i in range(1, H + 1):
        for j in range(1, W + 1):
            tot0 += grid1[i][j] == 0

    # 對恰好被覆蓋一次的格子數做二維前綴和
    grid2 = [[0] * (W + 2) for _ in range(H + 2)]
    for i in range(1, H + 1):
        for j in range(1, W + 1):
            grid2[i][j] = (
                grid2[i - 1][j]
                + grid2[i][j - 1]
                - grid2[i - 1][j - 1]
                + (grid1[i][j] == 1)
            )

    # 移除某朵雲會減少覆蓋數量為二維區間中恰好被覆蓋一次的格子數
    ans = []
    for x1, x2, y1, y2 in clouds:
        cur = tot0 + (
            grid2[x2][y2]
            - grid2[x1 - 1][y2]
            - grid2[x2][y1 - 1]
            + grid2[x1 - 1][y1 - 1]
        )
        ans.append(cur)
    print(*ans, sep="\n")


if __name__ == "__main__":
    solve()

寫在最後

Cover Image Credit

The cover image was created by @floomf. All rights belong to the original artist.

It is used here only as a non-commercial cover illustration for this note. I do not claim ownership of the artwork.

If you are the copyright holder and believe this usage is inappropriate, please contact me by email or leave a comment. I will remove the image promptly.