library_checker/data_structure/
point_set_range_composite.rs1use competitive::prelude::*;
2#[doc(no_inline)]
3pub use competitive::{
4 algebra::LinearOperation,
5 data_structure::SegmentTree,
6 num::{MInt, mint_basic::MInt998244353},
7};
8
9competitive::define_enum_scan! {
10 enum Query: usize {
11 0 => Set { p: usize, cd: (MInt998244353, MInt998244353) }
12 1 => Apply { l: usize, r: usize, x: MInt998244353 }
13 }
14}
15
16#[verify::library_checker("point_set_range_composite")]
17pub fn point_set_range_composite(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, ab: [(MInt998244353, MInt998244353); n]);
21 let mut seg = SegmentTree::<LinearOperation<_>>::from_vec(ab);
22 for _ in 0..q {
23 scan!(scanner, query: Query);
24 match query {
25 Query::Set { p, cd } => {
26 seg.set(p, cd);
27 }
28 Query::Apply { l, r, x } => {
29 let (a, b) = seg.fold(l..r);
30 writeln!(writer, "{}", a * x + b).ok();
31 }
32 }
33 }
34}