けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

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

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

問題概要

二次元平面上に  N 個の点がある。 i 番目の点の座標は  (X_{i}, Y_{i}) である。

「x 座標が  a 以上  c 以下で、y 座標が  b 以上  d 以下であるような点は何個あるか?」

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

制約

  •  1 \le N, Q \le 10^{5}
  •  1 \le X_{i}, Y_{i} \le 1500

解法

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;
    }
}