問題の説明

n x n のグリッド上に m 枚のカーペットが置かれています。これらのカーペットの情報が与えられたとき、各マスが何枚のカーペットで覆われているかを求めてください。

入力形式

第一行に、2つの正の整数 n, m が与えられます。

続く m 行に、それぞれ 2 つの座標 (x1, y1) と (x2, y2) が与えられます。これは、左上のマスが (x1, y1)、右下のマスが (x2, y2) であるカーペットを表します。

出力形式

n 行の出力をします。各行に n 個の整数を含みます。

i 行目の j 列目の整数は、マス (i, j) が覆われているカーペットの数を表します。

サンプル入力 1

5 3
2 2 3 3
3 3 5 5
1 2 1 4

サンプル出力 1

0 1 1 1 0
0 1 1 0 0
0 1 2 1 1
0 0 1 1 1
0 0 1 1 1

解説

この問題を解くには、各カーペットの範囲内のすべてのマスに 1 を加算する操作を m 回繰り返す必要があります。この操作を愚直に行うと、時間計算量は O(m * n^2) となり、n と m が最大 1000 であるため、時間切れになります。

より効率的な方法として、2次元差分配列 (2D Difference Array) を使用します。この手法では、各カーペットの範囲を O(1) でマークし、最後に全体の累積和を一度計算することで、最終的なグリッドを O(n^2) で構築できます。

具体的なマークの仕方は以下の通りです。カーペットの範囲が (top_left_row, top_left_col) から (bottom_right_row, bottom_right_col) の場合、差分配列 diff に対して以下の操作を行います。

• diff[top_left_row][top_left_col] += 1
• diff[top_left_row][bottom_right_col + 1] -= 1
• diff[bottom_right_row + 1][top_left_col] -= 1
• diff[bottom_right_row + 1][bottom_right_col + 1] += 1

これらの操作により、指定された矩形領域内のすべてのマスに 1 を加算する効果が得られます。最後に、この差分配列に対して 2 次元累積和を計算することで、各マスが実際に何枚のカーペットで覆われているかを求めることができます。

コード例 1 (差分配列を明示的に使用)

#include <iostream>
#include <cstring>
using namespace std;

const int MAX_SIZE = 1010;

int main() {
    int grid_size, carpet_count;
    cin >> grid_size >> carpet_count;

    // 差分配列を 0 で初期化
    int diff[MAX_SIZE][MAX_SIZE] = {0};

    // m 枚のカーペットの情報を処理
    for (int i = 0; i < carpet_count; ++i) {
        int top_left_row, top_left_col, bottom_right_row, bottom_right_col;
        cin >> top_left_row >> top_left_col >> bottom_right_row >> bottom_right_col;

        // 差分配列にマークを加える
        diff[top_left_row][top_left_col] += 1;
        diff[top_left_row][bottom_right_col + 1] -= 1;
        diff[bottom_right_row + 1][top_left_col] -= 1;
        diff[bottom_right_row + 1][bottom_right_col + 1] += 1;
    }

    // 差分配列から元の配列を復元し、出力する
    for (int i = 1; i <= grid_size; ++i) {
        for (int j = 1; j <= grid_size; ++j) {
            // 2次元累積和を計算
            diff[i][j] = diff[i][j] + diff[i-1][j] + diff[i][j-1] - diff[i-1][j-1];
            cout << diff[i][j] << " ";
        }
        cout << endl;
    }

    return 0;
}

コード例 2 (元の配列を差分配列として使用)

元の配列がすべて 0 で初期化されている場合、それ自体を差分配列として利用できます。これにより、余分な配列を確保する必要がなくなり、メモリ使用量を節約できます。

#include <iostream>
#include <cstring>
using namespace std;

const int MAX_SIZE = 1010;

int main() {
    int grid_size, carpet_count;
    cin >> grid_size >> carpet_count;

    // 元の配列（差分配列としても使用）を 0 で初期化
    int grid[MAX_SIZE][MAX_SIZE] = {0};

    // m 枚のカーペットの情報を処理
    for (int i = 0; i < carpet_count; ++i) {
        int top_left_row, top_left_col, bottom_right_row, bottom_right_col;
        cin >> top_left_row >> top_left_col >> bottom_right_row >> bottom_right_col;

        // 差分配列にマークを加える
        grid[top_left_row][top_left_col] += 1;
        grid[top_left_row][bottom_right_col + 1] -= 1;
        grid[bottom_right_row + 1][top_left_col] -= 1;
        grid[bottom_right_row + 1][bottom_right_col + 1] += 1;
    }

    // 差分配列から元の配列を復元し、出力する
    for (int i = 1; i <= grid_size; ++i) {
        for (int j = 1; j <= grid_size; ++j) {
            // 2次元累積和を計算
            grid[i][j] = grid[i][j] + grid[i-1][j] + grid[i][j-1] - grid[i-1][j-1];
            cout << grid[i][j] << " ";
        }
        cout << endl;
    }

    return 0;
}