blog.bouzuya.net

2023-09-15 口が痛い / AtCoder Library Practice Contest K を解いた

口が痛い。

  • Range Affine Range Sum (AtCoder Library Practice Contest:K問題) https://atcoder.jp/contests/practice2/tasks/practice2_k
    • https://atcoder.jp/contests/practice2/submissions/45548471
    • 解説 AC
    • 遅延セグメント木 (lazysegtree)
    • 言われるがままに実装して解いた
    • + c の部分がどれだけの個数分になるか分からないので個数も持たないといけない、とのこと
    • 遅延セグ木の問題はそれが適用できることや何を値データ・遅延データに持ちどういう演算するのかを考えられないとダメっぽい……
use lazysegtree::*;
use modint::ModInt998244353 as ModInt;
use proconio::input;
use segtree::*;

fn main() {
    input! {
        n: usize,
        q: usize,
        a: [usize; n],
    }
    type M = (ModInt, usize);
    impl Monoid for M {
        type S = M;
        fn identity() -> Self::S {
            (ModInt::new(0), 0_usize)
        }
        fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S {
            (a.0 + b.0, a.1 + b.1)
        }
    }
    struct F;
    impl MapMonoid for F {
        type M = M;
        type F = (ModInt, ModInt);
        fn identity_map() -> Self::F {
            (ModInt::new(1), ModInt::new(0))
        }
        fn mapping(&f: &Self::F, &x: &<Self::M as Monoid>::S) -> <Self::M as Monoid>::S {
            (f.0 * x.0 + f.1 * x.1, x.1)
        }
        fn composition(&f: &Self::F, &g: &Self::F) -> Self::F {
            (f.0 * g.0, f.0 * g.1 + f.1)
        }
    }

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

// lazysegtree
// modint

今日のコミット。