ABC038 を解いた。 D でうまくソートしたあと LIS: Longest Increasing Subsequence (最長増加部分列) の長さを求める問題が出ていた (解説では BIT が使われている) 。

末尾と比較して大きければ追加し、そうでないなら次以降のために最適な位置を更新している。計算量を下げるためにここで二分探索を使っている。あまり考えていない。最大個数分だけ確保して INF に初期化しておくと if がなくなるので良いかもしれない。あとで更新するかもしれない。

fn lis_length(a: &Vec<i64>, inf: i64) -> usize {
    let mut len = 0;
    let mut l = vec![inf; a.len()];
    for &a_i in a.iter() {
        let i = l.binary_search(&a_i).map_or_else(|i| i, |i| i);
        l[i] = a_i;
        len = std::cmp::max(len, i + 1);
    }
    len
}

https://atcoder.jp/contests/abc038/submissions/14066629

いろいろと家事をこなして避けられないイベントをこなしたらもう夜だ……。 Amazon でドッキングステーションやいくつかの工具や包丁・まな板などを買った。またいくつか書くかもしれない。