library_checker/data_structure/
range_affine_range_sum.rs1use competitive::prelude::*;
2use competitive::{
3 algebra::RangeSumRangeLinear, data_structure::LazySegmentTree,
4 num::mint_basic::MInt998244353 as M,
5};
6
7competitive::define_enum_scan! {
8 enum Query: usize {
9 0 => Update { l: usize, r: usize, bc: (M, M) }
10 1 => Fold { l: usize, r: usize }
11 }
12}
13
14#[verify::library_checker("range_affine_range_sum")]
15pub fn range_affine_range_sum(reader: impl Read, writer: impl Write) {
16 prepare_io!(reader, writer);
17 sc!(n, q, a: [M; iter n]);
18 let mut seg = LazySegmentTree::<RangeSumRangeLinear<_>>::from_keys(a);
19 for _ in 0..q {
20 sc!(query: Query);
21 match query {
22 Query::Update { l, r, bc } => {
23 seg.update(l..r, bc);
24 }
25 Query::Fold { l, r } => {
26 pp!(seg.fold(l..r).0);
27 }
28 }
29 }
30}