Skip to main content

library_checker/data_structure/
range_affine_range_sum.rs

1use competitive::prelude::*;
2#[doc(no_inline)]
3pub use competitive::{
4    algebra::RangeSumRangeLinear,
5    data_structure::LazySegmentTree,
6    num::{MInt, One, mint_basic::MInt998244353},
7};
8
9competitive::define_enum_scan! {
10    enum Query: usize {
11        0 => Update { l: usize, r: usize, bc: (MInt998244353, MInt998244353) }
12        1 => Fold { l: usize, r: usize }
13    }
14}
15
16#[verify::library_checker("range_affine_range_sum")]
17pub fn range_affine_range_sum(reader: impl Read, mut writer: impl Write) {
18    let s = read_all_unchecked(reader);
19    let mut scanner = Scanner::new(&s);
20    scan!(scanner, n, q, a: [MInt998244353]);
21    let mut seg = LazySegmentTree::<RangeSumRangeLinear<_>>::from_vec(
22        a.take(n).map(|x| (x, MInt998244353::one())).collect::<_>(),
23    );
24    for _ in 0..q {
25        scan!(scanner, query: Query);
26        match query {
27            Query::Update { l, r, bc } => {
28                seg.update(l..r, bc);
29            }
30            Query::Fold { l, r } => {
31                writeln!(writer, "{}", seg.fold(l..r).0).ok();
32            }
33        }
34    }
35}