AtCoder Beginner Contest 354 F

https://atcoder.jp/contests/abc354/tasks/abc354_f

まず、Aを左から見ていって、その要素が最大で増加部分列の何番目になるかを調べます。そのとき、その要素より小さい要素が最大何番目になっているかを調べます。そのために同じ番目で最小の要素を調べておきます。そうすると、二分探索が使えて、この部分がになります。
次に、逆から見て、最長の長さからはじめて、その要素の番目+1でその要素より大きいものがあれば、その要素は最長増加部分列に含まれます。

// Useless for LIS
#![allow(non_snake_case)]

use std::cmp::{min, max};


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect()
}


//////////////////// process ////////////////////

type Case = Vec<i32>;

fn read_case() -> Case {
    let _N: usize = read();
    let A: Case = read_vec();
    A
}

fn bin_search(first: usize, last: usize, a: i32, mins: &Vec<i32>) -> usize {
    let mid = (first + last) / 2;
    if last - first == 1 {
        first
    }
    else if mins[mid] < a {
        bin_search(mid, last, a, mins)
    }
    else {
        bin_search(first, mid, a, mins)
    }
}

fn F_each(A: Case) {
    let N = A.len();
    let mut mins: Vec<i32> = vec![0];
    let mut lengths: Vec<usize> = vec![0; N];
    for (i, &a) in A.iter().enumerate() {
        let n = bin_search(0, mins.len(), a, &mins) + 1;
        if n < mins.len() {
            mins[n] = min(mins[n], a)
        }
        else {
            mins.push(a)
        }
        lengths[i] = n
    }
    
    let max_l = mins.len() - 1;
    let mut bs: Vec<bool> = vec![false; N];
    let mut maxs: Vec<i32> = vec![0; max_l+1];
    for i in (0..N).rev() {
        let l = lengths[i];
        bs[i] = l == max_l || A[i] < maxs[l+1];
        if bs[i] {
            maxs[l] = max(maxs[l], A[i])
        }
    }
    
    let v: Vec<String> = bs.into_iter().enumerate().filter(|&(_, b)| b).
                                map(|(i, _)| (i+1).to_string()).collect();
    println!("{}", v.len());
    println!("{}", v.join(" "))
}

fn F(T: usize) {
    for _ in 0..T {
        let A = read_case();
        F_each(A)
    }
}

fn main() {
    let T: usize = read();
    F(T)
}