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

🔗 🟠 ABC436C 2x2 Placing

Problem Statement

題意簡述

給定一個 $N \times N$ 的網格，初始為空。
依序進行 $M$ 個操作，第 $i$ 次操作嘗試在 $(R_i, C_i)$ 處放置一個覆蓋 $(R_i, C_i), (R_i+1, C_i), (R_i, C_i+1), (R_i+1, C_i+1)$ 的 $2 \times 2$ 方塊。
若滿足以下任一條件，則不執行該操作（不放置方塊）：

方塊超出網格邊界 (即 $R_i + 1 > N$ 或 $C_i + 1 > N$ )。
方塊覆蓋的 4 個格子中，有任意一格已被先前的方塊佔用。

求最終成功放置的方塊數量。

Constraints

約束條件

$2 \le N \le 10^9$
$1 \le M \le 2 \times 10^5$
$1 \le R_i, C_i \le N - 1$

思路：模擬 + 雜湊表

本題需要模擬方塊放置的過程。
主要挑戰在於網格大小 $N$ 可達 $10^9$ ，這意味著我們無法宣告一個 $N \times N$ 的二維陣列來記錄狀態 (MLE)。

然而，操作數量 $M$ 最多只有 $2 \times 10^5$ ，且每個成功放置的方塊只佔用 4 格。因此，被佔用的總格子數最多為 $4M$ (約 $8 \times 10^5$ )。這個數量級完全可以使用 雜湊表 (Python 中的 set) 來儲存所有「已佔用」的座標 $(r, c)$ 。

演算法流程：

初始化一個空的集合 vis。
對於每個操作 $(R_i, C_i)$ $(R_{i}, C_{i})$ ：
- 檢查目標 $2 \times 2$ 區域的 4 個座標是否已存在於 vis 中。
- 若無衝突，則將這 4 個座標加入 vis，並視為一次成功放置。
- (由於題目保證 $1 \le R_i, C_i \le N - 1$ ，不用檢查是否超出邊界)。
輸出結果。

複雜度分析

時間複雜度： $\mathcal{O}(M)$ 。每個操作僅涉及常數次 (4次) 的 Set 查詢與插入，Python 的 set 平均操作為 $O(1)$ 。
空間複雜度： $\mathcal{O}(M)$ 。最多儲存 $4M$ 個座標點。

Code

def solve():
    N, M = map(int, input().split())
    vis = set()
    for _ in range(M):
        r, c = map(int, input().split())
        if any((x, y) in vis for x in range(r, r + 2) for y in range(c, c + 2)):
            continue
        for x in range(r, r + 2):
            for y in range(c, c + 2):
                vis.add((x, y))
    print(len(vis) // 4)

if __name__ == "__main__":
    solve()