セグ木(RMQ)

[tipstar0125]

問題：https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_bf 解答：https://atcoder.jp/contests/tessoku-book/submissions/49212757

input! {
    N: usize,
    Q: usize
}
let mut seg = SegmentTree::<MaxMonoid>::new(N);
for _ in 0..Q {
    input! {
        t: usize
    }
    if t == 1 {
        input! {
            pos: usize1,
            x: usize
        }
        seg.set(pos, x);
    } else {
        input! {
            l: usize1,
            r: usize1
        }
        println!("{}", seg.prod(l, r));
    }
}

[tipstar0125]

ただの数字ではなく、タプルを乗せる場合の例 問題：https://atcoder.jp/contests/abc329/tasks/abc329_d 解答：https://atcoder.jp/contests/abc329/submissions/49212890

input! {
    N: usize,
    M: usize,
    A: [usize; M]
}

let mut seg = SegmentTree::<MaxMonoid>::new(N);
for &a in &A {
    let (x, _) = seg.get(a - 1);
    seg.set(a - 1, (x + 1, (a as isize) * -1));
    let (_, ans) = seg.all_prod();
    println!("{}", -ans);
}

モノイド設定

struct MaxMonoid;

impl Monoid for MaxMonoid {
    type S = (isize, isize);
    fn op(a: &Self::S, b: &Self::S) -> Self::S {
        std::cmp::max(*a, *b)
    }
    fn id() -> Self::S {
        (0, 0)
    }
}