Struct RangeSumRangeChminChmaxAdd

pub struct RangeSumRangeChminChmaxAdd<T> {
    pub sum: T,
    /* private fields */
}

Fields

sum: T

Implementations

impl<T> RangeSumRangeChminChmaxAdd<T>

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

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

Examples found in repository

crates/competitive/src/algebra/monoid_action.rs (line 555)

        fn single_agg(&key: &Self::Key) -> Self::Agg {
            Self::single(key, T::one())
        }
        fn act_key(&x: &Self::Key, a: &Self::Act) -> Self::Key {
            if <Self::ActMonoid as Unital>::is_unit(a) {
                x
            } else {
                x.max(a.lb).min(a.ub) + a.bias
            }
        }
        fn act_agg(x: &Self::Agg, a: &Self::Act) -> Option<Self::Agg> {
            Some(if <Self::ActMonoid as Unital>::is_unit(a) {
                x.clone()
            } else if x.size.is_zero() {
                Self::unit()
            } else if x.min == x.max || a.lb == a.ub || a.lb >= x.max || a.ub <= x.min {
                Self::single(x.min.max(a.lb).min(a.ub) + a.bias, x.size)
            } else if x.min2 == x.max {
                let mut x = x.clone();
                let min = x.min.max(a.lb) + a.bias;
                let max = x.max.min(a.ub) + a.bias;
                x.min = min;
                x.max2 = min;
                x.max = max;
                x.min2 = max;
                x.sum = min * x.n_min + max * x.n_max;
                x
            } else if a.lb < x.min2 && x.max2 < a.ub {
                let mut x = x.clone();
                let min = x.min.max(a.lb);
                let max = x.max.min(a.ub);
                x.sum = x.sum + (min - x.min) * x.n_min + (max - x.max) * x.n_max + a.bias * x.size;
                x.min = min + a.bias;
                x.max = max + a.bias;
                x.min2 = x.min2 + a.bias;
                x.max2 = x.max2 + a.bias;
                x
            } else {
                return None;
            })
        }

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

pub fn range_chmin_chmax_add_range_sum(reader: impl Read, mut writer: impl Write) {
    let s = read_all_unchecked(reader);
    let mut scanner = Scanner::new(&s);
    scan!(scanner, n, q, a: [Saturating<i64>; n]);
    let mut seg = LazySegmentTree::<RangeSumRangeChminChmaxAdd<Saturating<i64>>>::from_vec(
        a.iter()
            .map(|&a| RangeSumRangeChminChmaxAdd::single(a, Saturating(1)))
            .collect(),
    );
    for _ in 0..q {
        match scanner.scan::<usize>() {
            0 => {
                scan!(scanner, l, r, b: Saturating<i64>);
                seg.update(l..r, RangeChminChmaxAdd::chmin(b));
            }
            1 => {
                scan!(scanner, l, r, b: Saturating<i64>);
                seg.update(l..r, RangeChminChmaxAdd::chmax(b));
            }
            2 => {
                scan!(scanner, l, r, b: Saturating<i64>);
                seg.update(l..r, RangeChminChmaxAdd::add(b));
            }
            3 => {
                scan!(scanner, l, r);
                writeln!(writer, "{}", seg.fold(l..r).sum).ok();
            }
            _ => panic!("unknown query"),
        }
    }
}

Trait Implementations

impl<T: Clone> Clone for RangeSumRangeChminChmaxAdd<T>

fn clone(&self) -> RangeSumRangeChminChmaxAdd<T>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T: Debug> Debug for RangeSumRangeChminChmaxAdd<T>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T> Magma for RangeSumRangeChminChmaxAdd<T>

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

type T = RangeSumRangeChminChmaxAdd<T>

type of operands: $T$

fn operate(x: &Self::T, y: &Self::T) -> Self::T

binary operaion: $\circ$

fn reverse_operate(x: &Self::T, y: &Self::T) -> Self::T

fn operate_assign(x: &mut Self::T, y: &Self::T)

impl<T> MonoidAction for RangeSumRangeChminChmaxAdd<T>

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

type Key = T

type Agg = RangeSumRangeChminChmaxAdd<T>

type Act = RangeChminChmaxAdd<T>

type AggMonoid = RangeSumRangeChminChmaxAdd<T>

type ActMonoid = RangeChminChmaxAdd<T>

fn single_agg(key: &Self::Key) -> Self::Agg

fn act_key(x: &Self::Key, a: &Self::Act) -> Self::Key

fn act_agg(x: &Self::Agg, a: &Self::Act) -> Option<Self::Agg>

fn toggle(_x: &mut Self::Agg)

fn agg_unit() -> Self::Agg

fn act_unit() -> Self::Act

fn agg_operate(x: &Self::Agg, y: &Self::Agg) -> Self::Agg

fn act_operate(x: &Self::Act, y: &Self::Act) -> Self::Act

fn agg_operate_assign(x: &mut Self::Agg, y: &Self::Agg)

fn act_operate_assign(x: &mut Self::Act, y: &Self::Act)

impl<T: PartialEq> PartialEq for RangeSumRangeChminChmaxAdd<T>

fn eq(&self, other: &RangeSumRangeChminChmaxAdd<T>) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<T> Unital for RangeSumRangeChminChmaxAdd<T>

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

fn unit() -> Self::T

identity element: $e$

fn is_unit(x: &Self::T) -> bool

where <Self as Magma>::T: PartialEq,

fn set_unit(x: &mut Self::T)

impl<T> Associative for RangeSumRangeChminChmaxAdd<T>

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

impl<T: Eq> Eq for RangeSumRangeChminChmaxAdd<T>

impl<T> StructuralPartialEq for RangeSumRangeChminChmaxAdd<T>