LIS 復元つき

[rsk0315]

https://atcoder.jp/contests/arc133/submissions/29126095

fn lis<'a, T: Ord>(a: &'a [T]) -> (Vec<usize>, Vec<&'a T>) {
    let ord = index_order_by(&a, |(i, ai), (j, aj)| {
        ai.cmp(aj).then_with(|| j.cmp(&i))
    });

    let n = a.len();
    let mut st: VecSegtree<OpMax<_>> = vec![(0_usize, 0); n].into();

    let mut prev = vec![None; n];
    for i in ord {
        let cur = st.fold(0..i);
        if cur.1 > 0 {
            prev[i] = Some(cur.1 - 1);
        }
        *st.get_mut(i).unwrap() = (cur.0 + 1, i + 1);
    }

    let mut i = st.fold(..).1 - 1;
    let mut argmax = vec![i];
    while let Some(ni) = prev[i] {
        i = ni;
        argmax.push(i);
    }
    argmax.reverse();

    let max: Vec<_> = argmax.iter().map(|&i| a.get(i).unwrap()).collect();
    (argmax, max)
}