library_checker/datastructure/
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
9#[verify::library_checker("range_affine_range_sum")]
10pub fn range_affine_range_sum(reader: impl Read, mut writer: impl Write) {
11    let s = read_all_unchecked(reader);
12    let mut scanner = Scanner::new(&s);
13    scan!(scanner, n, q, a: [MInt998244353]);
14    let mut seg = LazySegmentTree::<RangeSumRangeLinear<_>>::from_vec(
15        a.take(n).map(|x| (x, MInt998244353::one())).collect::<_>(),
16    );
17    for _ in 0..q {
18        match scanner.scan::<usize>() {
19            0 => {
20                scan!(scanner, l, r, bc: (MInt998244353, MInt998244353));
21                seg.update(l..r, bc);
22            }
23            1 => {
24                scan!(scanner, l, r);
25                writeln!(writer, "{}", seg.fold(l..r).0).ok();
26            }
27            _ => panic!("unknown query"),
28        }
29    }
30}