competitive/data_structure/
slope_trick.rs

1#[derive(Debug, Clone, Default)]
2pub struct SlopeTrick {
3    left: std::collections::BinaryHeap<i64>,
4    right: std::collections::BinaryHeap<i64>,
5    addl: i64,
6    addr: i64,
7    minval: i64,
8}
9impl SlopeTrick {
10    /// Create empty
11    pub fn new() -> Self {
12        Default::default()
13    }
14    /// Create valley
15    ///
16    /// f(x) = max(n(x-a), n(a-x))
17    pub fn valley(a: i64, n: usize) -> Self {
18        let mut self_: Self = Default::default();
19        self_.left.extend(std::iter::repeat(a).take(n));
20        self_.right.extend(std::iter::repeat(a).take(n));
21        self_
22    }
23    fn push_left(&mut self, x: i64) {
24        self.left.push(x - self.addl);
25    }
26    fn push_right(&mut self, x: i64) {
27        self.right.push(-(x - self.addr));
28    }
29    fn peek_left(&self) -> Option<i64> {
30        self.left.peek().map(|x| x + self.addl)
31    }
32    fn peek_right(&self) -> Option<i64> {
33        self.right.peek().map(|x| -x + self.addr)
34    }
35    fn pop_left(&mut self) -> Option<i64> {
36        self.left.pop().map(|x| x + self.addl)
37    }
38    fn pop_right(&mut self) -> Option<i64> {
39        self.right.pop().map(|x| -x + self.addr)
40    }
41    /// min f(x)
42    pub fn minimum(&self) -> i64 {
43        self.minval
44    }
45    /// argmin_x f(x)
46    pub fn min_range(&self) -> (Option<i64>, Option<i64>) {
47        (self.peek_left(), self.peek_right())
48    }
49    /// f(x) += a
50    pub fn add_const(&mut self, a: i64) {
51        self.minval += a;
52    }
53    /// f(x) += max(0, (x-a))
54    pub fn add_ramp(&mut self, a: i64) {
55        if let Some(x) = self.peek_left() {
56            self.minval += (x - a).max(0);
57        }
58        self.push_left(a);
59        let x = self.pop_left().unwrap();
60        self.push_right(x);
61    }
62    /// f(x) += max(0, (a-x))
63    pub fn add_pmar(&mut self, a: i64) {
64        if let Some(x) = self.peek_right() {
65            self.minval += (a - x).max(0);
66        }
67        self.push_right(a);
68        let x = self.pop_right().unwrap();
69        self.push_left(x);
70    }
71    /// f(x) += |x-a|
72    pub fn add_abs(&mut self, a: i64) {
73        self.add_ramp(a);
74        self.add_pmar(a);
75    }
76    /// right to left accumulated minimum
77    ///
78    /// f'(x) := min f(y) (y >= x)
79    pub fn clear_left(&mut self) {
80        self.left.clear();
81        self.addl = 0;
82    }
83    /// left to right accumulated minimum
84    ///
85    /// f'(x) := min f(y) (y <= x)
86    pub fn clear_right(&mut self) {
87        self.right.clear();
88        self.addr = 0;
89    }
90    /// f'(x) := f(x-a)
91    pub fn shift(&mut self, a: i64) {
92        self.slide_minimum(a, a);
93    }
94    /// f'(x) := min f(y) (x-a <= y <= x-b)
95    pub fn slide_minimum(&mut self, a: i64, b: i64) {
96        assert!(a <= b);
97        self.addl += a;
98        self.addr += b;
99    }
100}
competitive/data_structure/slope_trick.rs

competitive/data_structure/
slope_trick.rs
