library_checker/datastructure/
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
9#[verify::library_checker("range_chmin_chmax_add_range_sum")]
10pub fn range_chmin_chmax_add_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: [Saturating<i64>; n]);
14    let mut seg = LazySegmentTree::<RangeSumRangeChminChmaxAdd<Saturating<i64>>>::from_vec(
15        a.iter()
16            .map(|&a| RangeSumRangeChminChmaxAdd::single(a, Saturating(1)))
17            .collect(),
18    );
19    for _ in 0..q {
20        match scanner.scan::<usize>() {
21            0 => {
22                scan!(scanner, l, r, b: Saturating<i64>);
23                seg.update(l..r, RangeChminChmaxAdd::chmin(b));
24            }
25            1 => {
26                scan!(scanner, l, r, b: Saturating<i64>);
27                seg.update(l..r, RangeChminChmaxAdd::chmax(b));
28            }
29            2 => {
30                scan!(scanner, l, r, b: Saturating<i64>);
31                seg.update(l..r, RangeChminChmaxAdd::add(b));
32            }
33            3 => {
34                scan!(scanner, l, r);
35                writeln!(writer, "{}", seg.fold(l..r).sum).ok();
36            }
37            _ => panic!("unknown query"),
38        }
39    }
40}