Struct SlopeTrick 

pub struct SlopeTrick {
    left: BinaryHeap<i64>,
    right: BinaryHeap<i64>,
    addl: i64,
    addr: i64,
    minval: i64,
}

Fields

left: BinaryHeap<i64>

right: BinaryHeap<i64>

addl: i64

addr: i64

minval: i64

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))

fn push_left(&mut self, x: i64)

Examples found in repository

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

    pub fn add_ramp(&mut self, a: i64) {
        if let Some(x) = self.peek_left() {
            self.minval += (x - a).max(0);
        }
        self.push_left(a);
        let x = self.pop_left().unwrap();
        self.push_right(x);
    }
    /// f(x) += max(0, (a-x))
    pub fn add_pmar(&mut self, a: i64) {
        if let Some(x) = self.peek_right() {
            self.minval += (a - x).max(0);
        }
        self.push_right(a);
        let x = self.pop_right().unwrap();
        self.push_left(x);
    }

fn push_right(&mut self, x: i64)

Examples found in repository

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

    pub fn add_ramp(&mut self, a: i64) {
        if let Some(x) = self.peek_left() {
            self.minval += (x - a).max(0);
        }
        self.push_left(a);
        let x = self.pop_left().unwrap();
        self.push_right(x);
    }
    /// f(x) += max(0, (a-x))
    pub fn add_pmar(&mut self, a: i64) {
        if let Some(x) = self.peek_right() {
            self.minval += (a - x).max(0);
        }
        self.push_right(a);
        let x = self.pop_right().unwrap();
        self.push_left(x);
    }

fn peek_left(&self) -> Option<i64>

Examples found in repository

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

    pub fn min_range(&self) -> (Option<i64>, Option<i64>) {
        (self.peek_left(), self.peek_right())
    }
    /// f(x) += a
    pub fn add_const(&mut self, a: i64) {
        self.minval += a;
    }
    /// f(x) += max(0, (x-a))
    pub fn add_ramp(&mut self, a: i64) {
        if let Some(x) = self.peek_left() {
            self.minval += (x - a).max(0);
        }
        self.push_left(a);
        let x = self.pop_left().unwrap();
        self.push_right(x);
    }

fn peek_right(&self) -> Option<i64>

Examples found in repository

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

    pub fn min_range(&self) -> (Option<i64>, Option<i64>) {
        (self.peek_left(), self.peek_right())
    }
    /// f(x) += a
    pub fn add_const(&mut self, a: i64) {
        self.minval += a;
    }
    /// f(x) += max(0, (x-a))
    pub fn add_ramp(&mut self, a: i64) {
        if let Some(x) = self.peek_left() {
            self.minval += (x - a).max(0);
        }
        self.push_left(a);
        let x = self.pop_left().unwrap();
        self.push_right(x);
    }
    /// f(x) += max(0, (a-x))
    pub fn add_pmar(&mut self, a: i64) {
        if let Some(x) = self.peek_right() {
            self.minval += (a - x).max(0);
        }
        self.push_right(a);
        let x = self.pop_right().unwrap();
        self.push_left(x);
    }

fn pop_left(&mut self) -> Option<i64>

Examples found in repository

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

    pub fn add_ramp(&mut self, a: i64) {
        if let Some(x) = self.peek_left() {
            self.minval += (x - a).max(0);
        }
        self.push_left(a);
        let x = self.pop_left().unwrap();
        self.push_right(x);
    }

fn pop_right(&mut self) -> Option<i64>

Examples found in repository

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

    pub fn add_pmar(&mut self, a: i64) {
        if let Some(x) = self.peek_right() {
            self.minval += (a - x).max(0);
        }
        self.push_right(a);
        let x = self.pop_right().unwrap();
        self.push_left(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.