abc217 d

わかったのでメモ

問題

atcoder.jp

解法

• クエリ1の時、切った場所を順序付き集合に入れていく。
• クエリ2の時、xの右側の切った場所、左側の切った場所を集合から取り出し、差を求めることで長さが得られる。
• これを繰り返す。

集合から検索し、取り出す実装が分からなかった。 C++ではsetに二分探索(lower_bound, upper_bound)が使えるらしい。

Rustでのsetの二分探索の代用

RustのBTreeSetにはrange関数が実装されている。 これを使ってxより大きい要素、xより小さい要素を取得できる。 (初めて知った。)

doc.rust-lang.org

また、BTreeSetではnext_backを使うことで後ろから要素(最大値)を取り出せる。 罠もあるっぽいので注意する。

maguro.dev - Rust の BTreeSet / BTreeMap で最大値を素早く取得する方法

解答

Submission #25619157 - AtCoder Beginner Contest 217

use proconio::input;
use std::collections::BTreeSet;

fn main() {
    input! {
        l: usize,
        q: usize,
        cx: [(usize, usize); q]
    };

    let mut set = BTreeSet::new();
    set.insert(0);
    set.insert(l);
    for (c, x) in cx {
        match c {
            1 => {
                set.insert(x);
            }
            2 => {
                let l = *set.range(..x).next_back().unwrap();
                let r = *set.range(x..).next().unwrap();
                let ans = r - l;
                println!("{}", ans);
            }
            _ => unreachable!(),
        }
    }
}