概要

\(N \times N\) の掲示板に、高橋君と青木君がそれぞれ複数の長方形の広告を貼ります。両者の広告が重なるマスの総数を求めます。

考察

この問題では、高橋君の広告と青木君の広告がそれぞれ複数あり、それぞれが長方形の領域を覆います。単純に考えると、すべての広告の組について重なりを一つずつ計算すれば解けそうですが、そのような全探索は最悪の場合 \(A \times B = 100 \times 100 = 10^4\) 回の比較が必要になり、さらに各広告の大きさが最大 \(N \times N = 500 \times 500 = 2.5 \times 10^5\) マスもあるため、愚直な方法では計算量が爆発してしまいます。

そこで、二次元累積和（いもす法の二次元版） を用いて、各広告がどのマスを覆っているかを効率的に記録します。具体的には、各広告に対応する区間に「+1」を加算し、その後累積和を取ることで、各マスが何個の広告に覆われているかを高速に求めることができます。

この方法を使えば、高橋君の広告による被覆回数と青木君の広告による被覆回数を別々に計算し、両方とも1以上であるマスを数えることで答えを得られます。

アルゴリズム

1. 高橋君のすべての広告について、二次元いもす法を用いて、各マスが何個の広告に含まれるかを計算。
2. 同様に、青木君の広告についても二次元いもす法を適用。
3. 各マスについて、高橋君の広告が1つ以上重なりかつ青木君の広告が1つ以上重なっている場合、そのマスはカウントする。
4. 最終的にカウントされたマスの数を出力。

二次元いもす法のポイント：

• 座標は1-indexedなので、配列操作時にインデックス調整を行う（例：grid[r1-1][c1-1]）。
• 区間加算のために、四隅の符号を反転させる処理を行う。
• 最後に縦→横（または横→縦）の順で累積和を取り、各マスのカウントを確定させる。

計算量

• 時間計算量: \(O(N^2 + A + B)\)
  • 各広告に対して定数時間で区間加算を行い、その後 \(N \times N\) のグリッドに対して累積和を2回取る。
• 空間計算量: \(O(N^2)\)
  • 高橋君と青木君の広告を記録するための二次元配列を使用。

実装のポイント

• 座標変換に注意（1-indexed → 0-indexed）。
• 二次元いもす法では、区間の端を適切に処理するために、範囲外アクセスを防ぐために if 条件を入れる必要がある。
• 最後の走査で、両方のグリッドにおいて値が1以上かどうかを判定することで、重なりを検出できる。

ソースコード

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    N = int(data[idx]); idx += 1
    A = int(data[idx]); idx += 1
    B = int(data[idx]); idx += 1
    
    # 高橋君の広告
    T = []
    for _ in range(A):
        r1 = int(data[idx]); idx += 1
        c1 = int(data[idx]); idx += 1
        r2 = int(data[idx]); idx += 1
        c2 = int(data[idx]); idx += 1
        T.append((r1, c1, r2, c2))
    
    # 青木君の広告
    Aoki = []
    for _ in range(B):
        r1 = int(data[idx]); idx += 1
        c1 = int(data[idx]); idx += 1
        r2 = int(data[idx]); idx += 1
        c2 = int(data[idx]); idx += 1
        Aoki.append((r1, c1, r2, c2))
    
    # 二次元累積和を使って高速化
    # 座標圧縮は不要（N<=1000で可能）
    # 各広告をビットマップ的に処理するより、区間加算＋最後に走査の方が良い
    
    # 高橋君の広告をすべて塗る（+1）
    grid = [[0] * (N+1) for _ in range(N+1)]
    
    for r1, c1, r2, c2 in T:
        grid[r1-1][c1-1] += 1
        if r2 < N:
            grid[r2][c1-1] -= 1
        if c2 < N:
            grid[r1-1][c2] -= 1
        if r2 < N and c2 < N:
            grid[r2][c2] += 1
    
    # 縦方向の累積和
    for i in range(N):
        for j in range(N):
            if i > 0:
                grid[i][j] += grid[i-1][j]
    
    # 横方向の累積和
    for i in range(N):
        for j in range(N):
            if j > 0:
                grid[i][j] += grid[i][j-1]
    
    # grid[i][j] now contains the number of Takahashi ads covering cell (i+1,j+1)
    
    # Now count how many cells are covered by at least one Takahashi ad AND at least one Aoki ad
    # We'll use another grid to mark Aoki coverage, then intersect
    
    aoki_grid = [[0] * (N+1) for _ in range(N+1)]
    
    for r1, c1, r2, c2 in Aoki:
        aoki_grid[r1-1][c1-1] += 1
        if r2 < N:
            aoki_grid[r2][c1-1] -= 1
        if c2 < N:
            aoki_grid[r1-1][c2] -= 1
        if r2 < N and c2 < N:
            aoki_grid[r2][c2] += 1
    
    # 縦方向の累積和
    for i in range(N):
        for j in range(N):
            if i > 0:
                aoki_grid[i][j] += aoki_grid[i-1][j]
    
    # 横方向の累積和
    for i in range(N):
        for j in range(N):
            if j > 0:
                aoki_grid[i][j] += aoki_grid[i][j-1]
    
    count = 0
    for i in range(N):
        for j in range(N):
            if grid[i][j] >= 1 and aoki_grid[i][j] >= 1:
                count += 1
                
    print(count)

if __name__ == "__main__":
    main()

---

この解説は qwen3-coder-480b によって生成されました。