Struct SlopeTrick

pub struct SlopeTrick { /* private fields */ }

Implementations

impl SlopeTrick

pub fn new() -> Self

Create empty

pub fn valley(a: i64, n: usize) -> Self

Create valley

f(x) = max(n(x-a), n(a-x))

pub fn minimum(&self) -> i64

min f(x)

pub fn min_range(&self) -> (Option<i64>, Option<i64>)

argmin_x f(x)

pub fn add_const(&mut self, a: i64)

f(x) += a

pub fn add_ramp(&mut self, a: i64)

f(x) += max(0, (x-a))

Examples found in repository

crates/competitive/src/data_structure/slope_trick.rs (line 73)

    pub fn add_abs(&mut self, a: i64) {
        self.add_ramp(a);
        self.add_pmar(a);
    }

pub fn add_pmar(&mut self, a: i64)

f(x) += max(0, (a-x))

Examples found in repository

crates/competitive/src/data_structure/slope_trick.rs (line 74)

    pub fn add_abs(&mut self, a: i64) {
        self.add_ramp(a);
        self.add_pmar(a);
    }

pub fn add_abs(&mut self, a: i64)

f(x) += |x-a|

pub fn clear_left(&mut self)

right to left accumulated minimum

f’(x) := min f(y) (y >= x)

pub fn clear_right(&mut self)

left to right accumulated minimum

f’(x) := min f(y) (y <= x)

pub fn shift(&mut self, a: i64)

f’(x) := f(x-a)

pub fn slide_minimum(&mut self, a: i64, b: i64)

f’(x) := min f(y) (x-a <= y <= x-b)

Examples found in repository

crates/competitive/src/data_structure/slope_trick.rs (line 92)

    pub fn shift(&mut self, a: i64) {
        self.slide_minimum(a, a);
    }

Trait Implementations

impl Clone for SlopeTrick

fn clone(&self) -> SlopeTrick

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for SlopeTrick

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

Formats the value using the given formatter.

impl Default for SlopeTrick

fn default() -> SlopeTrick

Returns the “default value” for a type.