鉄則本 A09 - Winter in ALGO Kingdom (2Q, ★4)

二次元いもす法！

• 問題へのリンク

問題概要

のグリッドにおいて、 日間雪が降った。

日目には、マス を左上とし、 を右上とする長方形領域に雪が 1 cm だけ降った (溶けないとする)。

最終的な各マスの積雪量を求めよ。

制約

• 
• 

解法

二次元いもす法をします。鉄則本の問題なので、鉄則本を参照。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int H, W, N;
    cin >> H >> W >> N;
    
    // いもす法の準備
    vector num(H + 1, vector(W + 1, 0));
    for (int i = 0; i < N; ++i) {
        int A, B, C, D;
        cin >> A >> B >> C >> D;
        --A, --B;
        ++num[A][B], --num[A][D], --num[C][B], ++num[C][D];
    }
    
    // いもす法の累積和
    for (int i = 0; i <= H; ++i) {
        for (int j = 0; j < W; ++j) num[i][j + 1] += num[i][j];
    }
    for (int j = 0; j <= W; ++j) {
        for (int i = 0; i < H; ++i) num[i + 1][j] += num[i][j];
    }
    
    // 出力
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) cout << num[i][j] << " ";
        cout << endl;
    }
}