Rustコトハジメ

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

【ABC106-D AtCoder Express 2】二次元累積和

D - AtCoder Express 2

ちなみに、二次元累積和を使うとさらに高速化できます。 それを用いるとO(N2+Q)が達成できますが、本問題ではここまでは要求されません。

その二次元累積和を使った別解で解いてしまいました。

問題

N個の駅がある。M本の電車が、LiからRiを運行している。Q個のPi,Pjが与えられるから、Pi,Pjに完全に含まれる運行区間の数を答えよ。

方針

毎回計算すると絶対に間に合わないので、累積和か何かを使うということはすぐにわかりました。

冷静になってみると、

lとrを運行してる時に、x[l][r]に1を立てることにすると、pとqの間の運行列車の数というのは、x[p..q][p..q]の1の数ということがわかります。すなわち、二次元累積和です。

実装

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));
    }
}

私の競プロ用ライブラリはこれです。

GitHub - akiradeveloper/rust-comp-snippets