AtCoder Beginner Contest 439 E

https://atcoder.jp/contests/abc439/tasks/abc439_e

ある凧を上げると、その両側で別個に考えられるので、その凧のところで最大いくつ凧が上げられるかというDPを使えばいいのではと思いつきます。
凧を(A, B)の辞書順でソートすると、

となります。要するに、今考えている凧より左で今の凧と干渉しない凧の中で最大のDPの値を得られればよいです。これを簡単に求めるためにやっぱり木を作ります。Bをソートして、その並びでdpの値をノードの値にして、Bより小さい範囲を求めて、その範囲でのノードの値で最大のものを求めればよいです。
コードのSegTreeはAIに汎用のものを書いてもらいました。1-basedになっていたのが気に入らなかったので、0-basedに書き換えました。モノイドは群から逆元を除いたようなものです。モノイドを書くのとこのSegTreeを補完するような構造体のメソッドを書くのに集中できます。

// Kite
#![allow(non_snake_case)]


//////////////////// 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()
}


//////////////////// SegTree ////////////////////

trait Monoid {
    type S: Clone;
    fn op(a: &Self::S, b: &Self::S) -> Self::S;
    fn e() -> Self::S;
}

struct SegTree<M: Monoid> {
    n: usize,
    size: usize,
    data: Vec<M::S>,
}

impl<M: Monoid> SegTree<M> {
    fn new(n: usize) -> Self {
        let size = n.next_power_of_two();
        SegTree {
            n,
            size,
            data: vec![M::e(); size*2-1],
        }
    }
    
    fn from(v: Vec<M::S>) -> Self {
        let n = v.len();
        let size = n.next_power_of_two();
        let mut data = vec![M::e(); size*2-1];
        for i in 0..n {
            data[i+size-1] = v[i].clone();
        }
        let mut seg = SegTree { n, size, data };
        for i in (0..size-1).rev() {
            seg.data[i] = M::op(&seg.data[2*i+1], &seg.data[2*i+2]);
        }
        seg
    }
    
    fn set(&mut self, mut i: usize, x: M::S) {
        i = i + self.size - 1;
        self.data[i] = x;
        while i != 0 {
            i = (i - 1) / 2;
            self.data[i] = M::op(&self.data[2*i+1], &self.data[2*i+2]);
        }
    }
    
    fn prod(&self, mut l: usize, mut r: usize) -> M::S {
        let mut sml = M::e();
        let mut smr = M::e();
        l = l + self.size - 1;
        r = r + self.size - 1;
        while l < r {
            if l % 2 == 0 {
                sml = M::op(&sml, &self.data[l]);
                l += 1;
            }
            if r % 2 == 0 {
                r -= 1;
                smr = M::op(&self.data[r], &smr);
            }
            l = (l - 1) / 2;
            r = (r - 1) / 2
        }
        M::op(&sml, &smr)
    }
    
    fn get(&self, i: usize) -> M::S {
        self.data[i+self.size-1].clone()
    }
}


//////////////////// Monoid ////////////////////

struct Max;
impl Monoid for Max {
    type S = u32;
    fn op(a: &Self::S, b: &Self::S) -> Self::S { *a.max(b) }
    fn e() -> Self::S { 0 }
}


//////////////////// Tree ////////////////////

struct Tree {
    seg: SegTree::<Max>,    // 凧の個数を保持する
    B: Vec<i32>,
}

impl Tree {
    fn size(&self) -> usize {
        self.B.len()
    }
    
    // 与えられた値未満のBの最大のindex
    fn find_B_index(&self, b: i32) -> usize {
        let mut first: usize = 0;
        let mut last: usize = self.B.len();
        while last - first > 1 {
            let mid = (first + last) / 2;
            if self.B[mid] >= b {
                last = mid
            }
            else {
                first = mid
            }
        }
        first
    }
    
    fn set(&mut self, b: i32, n: u32) {
        if b == self.B[0] {
            self.seg.set(0, n)
        }
        else {
            let index = self.find_B_index(b);
            self.seg.set(index+1, n)
        }
    }
    
    // 与えられた値未満のBの中で個数最大
    fn max(&self, b: i32) -> u32 {
        if b <= self.B[0] {
            return 0
        }
        
        let index = self.find_B_index(b);
        self.seg.prod(0, index+1)
    }
    
    fn max_all(&self) -> u32 {
        self.seg.prod(0, self.size())
    }
    
    fn create(kites: &Vec<Kite>) -> Self {
        let N = kites.len();
        let seg = SegTree::<Max>::new(N);
        let mut B: Vec<i32> = kites.iter().map(|&(_, b)| b).collect();
        B.sort();
        Tree { seg, B }
    }
}


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

type Kite = (i32, i32);

// Aが同じ凧を集める
fn groupby(kites: &Vec<Kite>) -> Vec<Vec<Kite>> {
    let mut v: Vec<Vec<Kite>> = vec![];
    let mut prev: Kite = (0, 0);
    let mut same_A: Vec<Kite> = vec![];
    for &kite in kites.iter() {
        if same_A.is_empty() || kite.0 == prev.0 {
            same_A.push(kite)
        }
        else {
            v.push(same_A);
            same_A = vec![kite]
        }
        prev = kite
    }
    v.push(same_A);
    v
}

fn read_kite() -> Kite {
    let v: Vec<i32> = read_vec();
    let (A, B) = (v[0], v[1]);
    (A, B)
}

fn read_input() -> Vec<Kite> {
    let N: usize = read();
    let kites: Vec<Kite> = (0..N).map(|_| read_kite()).collect();
    kites
}

fn F(mut kites: Vec<Kite>) -> u32 {
    kites.sort();
    let mut tree = Tree::create(&kites);
    let groups = groupby(&kites);
    for group in groups {
        let mut ns: Vec<u32> = vec![];
        for kite in group.iter() {
            // kiteがBより小さい中で最大の個数を求める
            let n = tree.max(kite.1);
            ns.push(n + 1)
        }
        // 最後にまとめて更新する
        for (n, (_, b)) in ns.into_iter().zip(group.into_iter()) {
            tree.set(b, n)
        }
    }
    tree.max_all()
}

fn main() {
    let kites = read_input();
    println!("{}", F(kites))
}