blog.bouzuya.net

2023-09-08 区間加算・区間最小値 (オリジナル問題) を解いた

use lazysegtree::*;
use proconio::input;
use segtree::*;

fn main() {
    input! {
        n: usize,
        a: [usize; n],
        q: usize,
    }
    struct MinAdd;
    impl MapMonoid for MinAdd {
        type M = Min<usize>;
        type F = usize;

        fn identity_map() -> Self::F {
            0
        }

        fn mapping(&f: &usize, &x: &usize) -> usize {
            f + x
        }

        fn composition(&f: &usize, &g: &usize) -> usize {
            f + g
        }
    }

    let mut lazysegtree = LazySegtree::<MinAdd>::new(n);
    for (i, a_i) in a.iter().copied().enumerate() {
        lazysegtree.set(i, a_i);
    }
    for _ in 0..q {
        input! {
            t: usize,
            l: usize,
            r: usize,
        }
        match t {
            1 => {
                input! {
                    x: usize,
                }
                lazysegtree.apply_range(l..r, x);
            }
            2 => {
                let ans = lazysegtree.prod(l..r);
                println!("{}", ans);
            }
            _ => unreachable!(),
        }
    }
}

// lazysegtree

今日のコミット。