AtCoder Beginner Contest 106 : 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) と聞き驚いた(間に合うんですね).