Struct RangeSumRangeChminChmaxAdd

Source

pub struct RangeSumRangeChminChmaxAdd<T> {
    min: T,
    max: T,
    min2: T,
    max2: T,
    pub sum: T,
    size: T,
    n_min: T,
    n_max: T,
}

Fields§

§min: T§max: T§min2: T§max2: T§sum: T§size: T§n_min: T§n_max: T

Implementations§

Source §

impl<T> RangeSumRangeChminChmaxAdd<T>
where T: Copy + Zero + One + Ord + Bounded + Add<Output = T> + Sub<Output = T> + Mul<Output = T> + PartialEq,

Source

pub fn single(key: T, size: T) -> Self

Examples found in repository ?

crates/competitive/src/algebra/lazy_map.rs (line 523)

522    fn single_agg(&key: &Self::Key) -> Self::Agg {
523        Self::single(key, T::one())
524    }
525    fn act_agg(x: &Self::Agg, a: &Self::Act) -> Option<Self::Agg> {
526        Some(if <Self::ActMonoid as Unital>::is_unit(a) {
527            x.clone()
528        } else if x.size.is_zero() {
529            Self::unit()
530        } else if x.min == x.max || a.lb == a.ub || a.lb >= x.max || a.ub <= x.min {
531            Self::single(x.min.max(a.lb).min(a.ub) + a.bias, x.size)
532        } else if x.min2 == x.max {
533            let mut x = x.clone();
534            let min = x.min.max(a.lb) + a.bias;
535            let max = x.max.min(a.ub) + a.bias;
536            x.min = min;
537            x.max2 = min;
538            x.max = max;
539            x.min2 = max;
540            x.sum = min * x.n_min + max * x.n_max;
541            x
542        } else if a.lb < x.min2 && x.max2 < a.ub {
543            let mut x = x.clone();
544            let min = x.min.max(a.lb);
545            let max = x.max.min(a.ub);
546            x.sum = x.sum + (min - x.min) * x.n_min + (max - x.max) * x.n_max + a.bias * x.size;
547            x.min = min + a.bias;
548            x.max = max + a.bias;
549            x.min2 = x.min2 + a.bias;
550            x.max2 = x.max2 + a.bias;
551            x
552        } else {
553            return None;
554        })
555    }

More examples

Hide additional examples

crates/library_checker/src/data_structure/range_chmin_chmax_add_range_sum.rs (line 16)

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            _ => unreachable!("unknown query"),
38        }
39    }
40}