きろく

特筆すべき記録のまとめ

AtCoder Beginner Contest 106 : D - AtCoder Express 2

問題

D - AtCoder Express 2

東西に伸びる線路に都市が N 個あり,M 本の列車が都市 L_i と R_i の間を走っている.以下のクエリが Q 個与えられるので,それらに答える問題:都市 p_i と q_i の区間に走る区間が完全に含まれる列車の数.

N <= 500, M <= 200000, Q <= 100000.

解法

求めたい列車の数は,(A ~ B) で都市 A と B の間を走っている列車の合計とすると,

(p_i ~ p_i) + (p_i ~ p_i + 1) + ... + (p_i ~ q_i) +

(p_i + 1 ~ p_i + 1) + (p_i + 1 ~ p_i + 2) + ... + (p_i + 1 ~ q_i) +

...

となる.これを二次元平面上にプロットすると長方形になっていて,この長方形の中にある数の合計を求めればよいとなる.

ここまで考察が進むと二次元累積和が考えられて,前処理 O(N^2) のあとクエリ O(1)

 で処理できるので,全体で O(N^2 + Q) となる.これが想定解だと思っていたら,想定解は O(NQ) と聞き驚いた(間に合うんですね).

解答

Submission #3036755 - AtCoder Beginner Contest 106

f:id:babcs2035:20180819214756p:plain

gist.github.com