bouzuya.hatenablog.com

ぼうずやのにっき

口が痛い / AtCoder Library Practice Contest L を解いた

口が痛い。 Slay the Spire をプレイしたい気持ちが戻ってきている。

bouzuya/genpi に crates:tracing を入れて動きを確認している。

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

fn main() {
    input! {
        n: usize,
        q: usize,
        a: [usize; n],
        tlr: [(usize, usize, usize); q],
    }

    type M = (usize, usize, usize);
    impl Monoid for M {
        type S = M;
        fn identity() -> Self::S {
            (0, 0, 0)
        }
        fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S {
            (a.0 + b.0, a.1 + b.1, a.2 + b.2 + a.1 * b.0)
        }
    }

    struct F;
    impl MapMonoid for F {
        type M = M;
        type F = bool;
        fn identity_map() -> Self::F {
            false
        }
        fn mapping(&f: &Self::F, &x: &<Self::M as Monoid>::S) -> <Self::M as Monoid>::S {
            if f {
                (x.1, x.0, x.0 * x.1 - x.2)
            } else {
                x
            }
        }
        fn composition(&f: &Self::F, &g: &Self::F) -> Self::F {
            f ^ g
        }
    }

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

// lazysegtree

今日のコミット。