概要

\(N \times N\) のグリッド上に貼られた高橋君の複数の長方形広告と青木君の複数の長方形広告について、少なくとも1つずつの広告に覆われているマスの数を求める問題です。

考察

各マスについて、高橋君の広告のいずれかと青木君の広告のいずれかの両方に覆われているかを調べれば答えが得られます。しかし、単純に各広告の組み合わせに対して重なりを計算すると、最大 \(A \times B = 10000\) 通りの組み合わせについて重なりを計算する必要があり、さらに各重なり領域のマス数を数えると時間がかかります。また、同じマスが複数の組み合わせで重複してカウントされるため、重複を排除する必要もあります。

そこで、効率的に計算するために、二次元累積和を用いて各マスが高橋君の広告に何枚覆われているか、青木君の広告に何枚覆われているかを別々に計算します。これにより、各マスについて高橋君と青木君の広告の被覆状況を \(O(1)\) で調べられるようになります。

アルゴリズム

1. 二次元いもす法を用いて、高橋君の広告群による各マスの被覆枚数と、青木君の広告群による各マスの被覆枚数を別々に計算します。
   • 各広告に対して、左上 \((r1, c1)\) に +1、右上 \((r1, c2+1)\) に -1、左下 \((r2+1, c1)\) に -1、右下 \((r2+1, c2+1)\) に +1 を加算します。
2. 次に、二次元累積和を取ることで、各マス \((i, j)\) についての被覆枚数を求めます。
   • \(board[i][j] = board[i][j] + board[i-1][j] + board[i][j-1] - board[i-1][j-1]\)
3. 最後に、各マスについて高橋君の被覆枚数が1以上かつ青木君の被覆枚数が1以上であるかを調べ、条件を満たすマスの数を数えます。

計算量

• 時間計算量: \(O(N^2 + A + B)\)
  • いもす法の加算処理: \(O(A + B)\)
  • 累積和の計算: \(O(N^2)\)
  • マスのチェック: \(O(N^2)\)
• 空間計算量: \(O(N^2)\)

実装のポイント

• グリッドのサイズが \(N \leq 500\) なので、二次元配列を \(500 \times 500\) で確保すれば十分です。ただし、累積和を取る際に範囲外参照を防ぐため、配列を \((N+2) \times (N+2)\) で確保しています。
• いもす法では、広告の右下の次のマスに加算するため、インデックスに注意が必要です（\(r2+1\), \(c2+1\)）。
• 累積和を取る際は、1-indexedでループを回すと実装が簡単です。

ソースコード

def main():
    import sys
    data = sys.stdin.read().split()
    idx = 0
    N = int(data[idx]); A = int(data[idx+1]); B = int(data[idx+2]); idx += 3
    
    board_t = [[0] * (N+2) for _ in range(N+2)]
    board_a = [[0] * (N+2) for _ in range(N+2)]
    
    for i in range(A):
        r1 = int(data[idx]); c1 = int(data[idx+1]); r2 = int(data[idx+2]); c2 = int(data[idx+3]); idx += 4
        board_t[r1][c1] += 1
        board_t[r1][c2+1] -= 1
        board_t[r2+1][c1] -= 1
        board_t[r2+1][c2+1] += 1
        
    for j in range(B):
        r1 = int(data[idx]); c1 = int(data[idx+1]); r2 = int(data[idx+2]); c2 = int(data[idx+3]); idx += 4
        board_a[r1][c1] += 1
        board_a[r1][c2+1] -= 1
        board_a[r2+1][c1] -= 1
        board_a[r2+1][c2+1] += 1
        
    for i in range(1, N+1):
        for j in range(1, N+1):
            board_t[i][j] += board_t[i-1][j] + board_t[i][j-1] - board_t[i-1][j-1]
            board_a[i][j] += board_a[i-1][j] + board_a[i][j-1] - board_a[i-1][j-1]
            
    count = 0
    for i in range(1, N+1):
        for j in range(1, N+1):
            if board_t[i][j] > 0 and board_a[i][j] > 0:
                count += 1
                
    print(count)

if __name__ == "__main__":
    main()

---

この解説は deepseekv3 によって生成されました。