library_checker/data_structure/
range_chmin_chmax_add_range_sum.rs

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

library_checker/data_structure/range_chmin_chmax_add_range_sum.rs

library_checker/data_structure/
range_chmin_chmax_add_range_sum.rs