Rustコトハジメ

プログラミング言語Rustと競プロに関する情報をお届けします。

【ABC106-D AtCoder Express 2】気づけば単なる二次元累積和

実装含めて30分くらいはかかってしまった。慣れてる人なら10分以内で解くでしょう典型問題。

D - AtCoder Express 2

問題

N(500)の駅がある。M(20万)本の列車はそれぞれ、駅lと駅rの中を走る。

Q(20万)個の問い「走行区間がp,qに完全に含まれる列車の本数は?」に対して答えよ。

方針

あーAtCoder Expressの悪夢再びー。しかし全く違う問題やんけ。

形としては、

D - Recording

に似てるので、同じように数え上げるのか?と思ったがどうも違う。

その延長で範囲加算RMQも考えたが、最小値を出したところで何の意味もありそうになかった。

結局、まずは各lごとにN本の累積和を考えることにして、そしたらlごとに本数はO(1)でわかるが、結局各クエリがO(N)になって死ぬという誤りに気づいた。

しかしその過程で、はっ・・・二次元累積和で良いのではと気づいた。僥倖。

実装

fn solve() {
    input!{
        N:usize,M:usize,Q:usize,
        LR:[(usize,usize);M],
        PQ:[(usize,usize);Q],
    }
    let mut lr = vec![vec![0;N+1];N+1];
    for (l,r) in LR{
        lr[l][r] += 1;
    }
    let cum = Cum2::build(&lr);
    for (p,q) in PQ{
        println!("{}",cum.query(p,q,p,q));
    }
}

考察

1次元っぽく見える区間という概念を2次元のマスに当てはめて二次元累積和にするというところに飛躍がある。