【AtCoder】ABC 482 C - Band Count

2026-11-04

AtCoder/ABC/C問題 AtCoder/ABC/300点問題 AtCoder/茶Diff AtCoder/NoviSteps/2Q 競技プログラミング

C - Band Count

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

実行時間制限: 2 sec / メモリ制限: 1024 MiB / Difficulty: 486 / NoviSteps: 2Q / 配点: 300 点

問題概要

$H \times W$ のグリッドがあり、上から $i$ 行目、左から $j$ 列目のマスを $(i,j)$ とする。

グリッドには $N$ 個の駒が置かれており、 $i$ 番目の駒は $(R_i, C_i)$ にある。

$Q$ 個のクエリに答えよ。クエリは以下の $2$ 種類ある。

1 u d: $u$ 行目から $d$ 行目までに置かれている駒の個数を出力する。
2 l r: $l$ 列目から $r$ 列目までに置かれている駒の個数を出力する。

制約

$1 \leq H, W \leq 10^9$
$1 \leq N \leq \min(H \times W, 3 \times 10^5)$
$1 \leq R_i \leq H$
$1 \leq C_i \leq W$
$i \neq j$ ならば $(R_i, C_i) \neq (R_j, C_j)$
$1 \leq Q \leq 3 \times 10^5$
$1 \leq u \leq d \leq H$
$1 \leq l \leq r \leq W$
入力される値は全て整数

考察

2種類のクエリは互いの答えに影響しないので、行と列を独立に考えることができる。

行方向について、駒が置かれている行番号を昇順にソートした配列 $R$ を用意する。

すると、クエリ1では

$R$ の要素の中で、 $u$ 以上 $d$ 以下の要素の個数

を求めればよい。

これは $d$ 以下の要素数から $u$ 未満の要素数を引くことに相当し、lower_bound と upper_bound を使って二分探索で求めることができる。

列方向も同様に処理できるので、全体としては $O(Q \log N)$ の計算量で解くことができる。

実装例

1.#include <bits/stdc++.h>
2.using namespace std;
3. 
4.#define all(x) (x).begin(), (x).end()
5.#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)
6. 
7.// ======================================== //
8. 
9.int main()
10.{
11.    int H, W, N, Q;
12.    cin >> H >> W >> N >> Q;
13.    vector<int> R(N), C(N);
14.    rep(i, 0, N) cin >> R[i] >> C[i];
15. 
16.    sort(all(R));
17.    sort(all(C));
18. 
19.    while (Q--) {
20.        int t;
21.        cin >> t;
22. 
23.        if (t == 1) {
24.            int u, d;
25.            cin >> u >> d;
26. 
27.            int a = lower_bound(all(R), u) - R.begin();
28.            int b = upper_bound(all(R), d) - R.begin();
29. 
30.            cout << b - a << endl;
31.        }
32.        else if (t == 2) {
33.            int l, r;
34.            cin >> l >> r;
35. 
36.            int a = lower_bound(all(C), l) - C.begin();
37.            int b = upper_bound(all(C), r) - C.begin();
38. 
39.            cout << b - a << endl;
40.        }
41.    }
42. 
43.    return 0;
44.}

https://atcoder.jp/contests/abc482/submissions/80504209

実装時間: 5 分

コメント

$H, W$ の値が大きいので、累積和配列を作ることはできないことに注意。