library_checker/data_structure/
range_chmin_chmax_add_range_sum.rs

1use competitive::prelude::*;
2#[doc(no_inline)]
3pub use competitive::{
4    algebra::{RangeChminChmaxAdd, RangeSumRangeChminChmaxAdd},
5    data_structure::LazySegmentTree,
6    num::Saturating,
7};
8
9competitive::define_enum_scan! {
10    enum Query: usize {
11        0 => Chmin { l: usize, r: usize, b: Saturating<i64> }
12        1 => Chmax { l: usize, r: usize, b: Saturating<i64> }
13        2 => Add { l: usize, r: usize, b: Saturating<i64> }
14        3 => Sum { l: usize, r: usize }
15    }
16}
17
18#[verify::library_checker("range_chmin_chmax_add_range_sum")]
19pub fn range_chmin_chmax_add_range_sum(reader: impl Read, mut writer: impl Write) {
20    let s = read_all_unchecked(reader);
21    let mut scanner = Scanner::new(&s);
22    scan!(scanner, n, q, a: [Saturating<i64>; n]);
23    let mut seg = LazySegmentTree::<RangeSumRangeChminChmaxAdd<Saturating<i64>>>::from_vec(
24        a.iter()
25            .map(|&a| RangeSumRangeChminChmaxAdd::single(a, Saturating(1)))
26            .collect(),
27    );
28    for _ in 0..q {
29        scan!(scanner, query: Query);
30        match query {
31            Query::Chmin { l, r, b } => {
32                seg.update(l..r, RangeChminChmaxAdd::chmin(b));
33            }
34            Query::Chmax { l, r, b } => {
35                seg.update(l..r, RangeChminChmaxAdd::chmax(b));
36            }
37            Query::Add { l, r, b } => {
38                seg.update(l..r, RangeChminChmaxAdd::add(b));
39            }
40            Query::Sum { l, r } => {
41                writeln!(writer, "{}", seg.fold(l..r).sum).ok();
42            }
43        }
44    }
45}

library_checker/data_structure/range_chmin_chmax_add_range_sum.rs

library_checker/data_structure/
range_chmin_chmax_add_range_sum.rs