鉄則本 B08 - Counting Points (2Q, ★4)

二次元累積和の練習問題！

• 問題へのリンク

問題概要

二次元平面上に 個の点がある。 番目の点の座標は である。

「x 座標が 以上 以下で、y 座標が 以上 以下であるような点は何個あるか？」

というタイプの 回のクエリに答えよ。

制約

• 
• 

解法

x, y 座標の値が小さいことに着目して、グリッドの問題だと捉えることができる。そして二次元累積和を活用しよう！

github.com

コード

#include <bits/stdc++.h>
using namespace std;
const int MAX = 1600;

int main() {
    // 個数と累積和
    vector num(MAX, vector(MAX, 0));
    vector S(MAX + 1, vector(MAX + 1, 0));
    
    // 入力
    int N, Q;
    cin >> N;
    for (int i = 0; i < N; ++i) {
        int X, Y;
        cin >> X >> Y;
        --X, --Y;
        ++num[X][Y];
    }
    
    // 二次元累積和を求める
    for (int i = 0; i < MAX; ++i) {
        for (int j = 0; j < MAX; ++j) {
            S[i + 1][j + 1] = S[i + 1][j] + num[i][j];
        }
    }
    for (int j = 0; j <= MAX; ++j) {
        for (int i = 0; i < MAX; ++i) {
            S[i + 1][j] += S[i][j];
        }
    }
    
    // クエリ
    cin >> Q;
    while (Q--) {
        int A, B, C, D;
        cin >> A >> B >> C >> D;
        --A, --B;
        
        int res = S[C][D] - S[A][D] - S[C][B] + S[A][B];
        cout << res << endl;
    }
}