概要

高橋君の広告で覆われるマス集合と、青木君の広告で覆われるマス集合をそれぞれ求め、両方に含まれる（重なっている）マス数を数えます。

考察

各広告は長方形なので、素朴に「長方形の中の全マスを 1 つずつ塗る」を各広告ごとに行うと、最悪で \(N^2\) に近い面積を \(A+B\) 回処理することになり、Python ではやや重くなりがちです（最大で約 \(200 \times 500 \times 500 = 50,000,000\) マス更新）。

また、広告同士の重なりを「高橋の各長方形 × 青木の各長方形」で調べる方針にすると、長方形同士の交差は計算できても「同じマスを複数回数えない」処理が面倒になります。

そこで重要な気づきは次の通りです。

• 欲しいのは 各マスが「高橋に1回以上覆われるか」「青木に1回以上覆われるか」 だけ（回数自体は不要、\(>0\) かどうかで良い）。
• 長方形の一括加算は、2 次元の差分配列（2D いもす法）で高速にできる。

これにより、各長方形を \(O(1)\) で差分配列へ反映し、最後に \(O(N^2)\) で全マスの被覆数を復元して重なりを数えられます。

アルゴリズム

高橋用・青木用にそれぞれ独立に 2D いもす法を行います。

1. 2D差分配列（いもす法）の更新

マス \((r, c)\) を 1-indexed とし、長方形 \((r_1,c_1)\)〜\((r_2,c_2)\) を「+1 で塗る」とき、差分配列 diff に次を加えます：

• diff[r1][c1] += 1
• diff[r1][c2+1] -= 1
• diff[r2+1][c1] -= 1
• diff[r2+1][c2+1] += 1

こうしておくと、後で 2 次元累積和を取ったときに、長方形領域だけが +1 されます。
境界の r2+1 や c2+1 を安全に扱うため、配列サイズを \((N+2)\times(N+2)\) にしています。

2. 累積和で被覆数を復元

diff から実際の被覆数 cover を得るには、2 次元累積和を取ります。実装では

1. 行方向に累積（横に足し上げる）
2. 列方向に累積（上から足し上げる）

の順で処理し、各マスの「その人の広告に何回覆われたか」を得ます。

3. 重なりマスを数える

全マス \((r,c)\) について

• 高橋の被覆数 coverA[r][c] > 0
• 青木の被覆数 coverB[r][c] > 0

の両方を満たすなら、そのマスは重なっているので答えに +1 します。
同じマスが複数広告で覆われても、条件は \(>0\) かどうかだけなので自然に「1 回だけ数える」ことになります。

計算量

• 時間計算量: \(O((A+B) + N^2)\)
  （長方形の差分更新が \(O(A+B)\)、累積和と集計が \(O(N^2)\)）
• 空間計算量: \(O(N^2)\)
  （高橋用・青木用の配列を保持）

実装のポイント

• 配列は \((N+2)\times(N+2)\) を確保し、r2+1 や c2+1 への更新を境界チェックなしで書けるようにします。

• いもす法の復元（累積和）は「横→縦」の 2 段階で OK です。

• 最後は > 0 判定で十分です（「少なくとも1つの広告に覆われる」条件をそのまま表せる）。

  ソースコード

import sys
from array import array

def build_cover(diff, n):
    # horizontal prefix
    for r in range(1, n + 1):
        row = diff[r]
        s = 0
        for c in range(1, n + 1):
            s += row[c]
            row[c] = s
    # vertical prefix
    for r in range(1, n + 1):
        row = diff[r]
        prev = diff[r - 1]
        for c in range(1, n + 1):
            row[c] += prev[c]

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    it = iter(data)
    N = next(it)
    A = next(it)
    B = next(it)

    W = N + 2
    diffA = [array('i', [0]) * W for _ in range(W)]
    diffB = [array('i', [0]) * W for _ in range(W)]

    for _ in range(A):
        r1 = next(it); c1 = next(it); r2 = next(it); c2 = next(it)
        diffA[r1][c1] += 1
        diffA[r1][c2 + 1] -= 1
        diffA[r2 + 1][c1] -= 1
        diffA[r2 + 1][c2 + 1] += 1

    for _ in range(B):
        r1 = next(it); c1 = next(it); r2 = next(it); c2 = next(it)
        diffB[r1][c1] += 1
        diffB[r1][c2 + 1] -= 1
        diffB[r2 + 1][c1] -= 1
        diffB[r2 + 1][c2 + 1] += 1

    build_cover(diffA, N)
    build_cover(diffB, N)

    ans = 0
    for r in range(1, N + 1):
        rowA = diffA[r]
        rowB = diffB[r]
        for c in range(1, N + 1):
            if rowA[c] > 0 and rowB[c] > 0:
                ans += 1

    print(ans)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。