AtCoder Express 2 [AtCoder Beginner Contest 106 D]

https://beta.atcoder.jp/contests/abc106/tasks/abc106_d

考察過程

1. O(MQ)はすぐに思いつくが、O(M)を改善したい
2. N≦500をうまく使って高速化したい
3. O(NQ)が理想っぽい。ここから考えると、各クエリについて左端を全探索できる
4. 右端については累積和で高速計算ができる
5. 大丈夫

解法

https://beta.atcoder.jp/contests/abc106/submissions/3040351

「cnt[L][R] := 区間[L,R]の列車の台数」とする。
これを使ってクエリに答える。
[p,q]のクエリに答えるには左端Lを[p,q]の範囲で全探索する。
左端をLとすると、cnt[L][L] + cnt[L][L+1] + ... + cnt[L][q]が左端がLで右端がq以下の列車の台数となる。
これをこのまま実装するとO(N^2Q)となるので、累積和を使って高速化しよう。
「cnt[L][R] := 区間[L,1], [L,2], ..., [L,R]の列車の台数」
これを使うと、左端Lのとき、cnt[L][q]が左端がLで右端がq以下の列車の台数となる。
これでO(NQ)でAC。

int N, M, Q;
int cnt[505][505];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M >> Q;
    rep(i, 0, M) {
        int L, R; cin >> L >> R;
        cnt[L][R]++;
    }
    rep(L, 1, N + 1) rep(R, 2, N + 1) cnt[L][R] += cnt[L][R - 1];
    rep(_, 0, Q) {
        int p, q; cin >> p >> q;
        int ans = 0;
        rep(L, p, q + 1) ans += cnt[L][q];
        printf("%d\n", ans);
    }
}