competitive/data_structure/
line_set.rs

1use super::Bounded;
2use std::{
3    borrow::Borrow,
4    cmp::Ordering,
5    collections::BTreeSet,
6    fmt::{self, Debug},
7    ops::{Add, Div, Mul, Sub},
8};
9
10#[derive(Clone, Copy, Default, PartialEq, Eq)]
11struct Slope<T>(T);
12
13impl<T> Debug for Slope<T>
14where
15    T: Debug,
16{
17    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
18        self.0.fmt(f)
19    }
20}
21
22impl<T> PartialOrd for Slope<T>
23where
24    T: PartialOrd,
25{
26    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
27        self.0.partial_cmp(&other.0).map(|ord| ord.reverse())
28    }
29}
30
31impl<T> Ord for Slope<T>
32where
33    T: Ord,
34{
35    fn cmp(&self, other: &Self) -> Ordering {
36        self.0.cmp(&other.0).reverse()
37    }
38}
39
40#[derive(Clone, Copy, Default, PartialEq, Eq, PartialOrd, Ord)]
41struct Query<T>(T);
42
43impl<T> Debug for Query<T>
44where
45    T: Debug,
46{
47    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
48        self.0.fmt(f)
49    }
50}
51
52#[derive(Debug, Clone, Default)]
53struct Line<T> {
54    a: Slope<T>,
55    b: T,
56    q: Query<T>,
57}
58
59impl<T> PartialEq for Line<T>
60where
61    T: PartialEq,
62{
63    fn eq(&self, other: &Self) -> bool {
64        self.a == other.a
65    }
66}
67
68impl<T> Eq for Line<T> where T: Eq {}
69
70impl<T> PartialOrd for Line<T>
71where
72    T: PartialOrd,
73{
74    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
75        self.a.partial_cmp(&other.a)
76    }
77}
78
79impl<T> Ord for Line<T>
80where
81    T: Ord,
82{
83    fn cmp(&self, other: &Self) -> Ordering {
84        self.a.cmp(&other.a)
85    }
86}
87
88impl<T> Borrow<Slope<T>> for Line<T> {
89    fn borrow(&self) -> &Slope<T> {
90        &self.a
91    }
92}
93
94impl<T> Borrow<Query<T>> for Line<T> {
95    fn borrow(&self) -> &Query<T> {
96        &self.q
97    }
98}
99
100impl<T> Line<T> {
101    fn new(a: T, b: T, q: T) -> Self {
102        Self {
103            a: Slope(a),
104            b,
105            q: Query(q),
106        }
107    }
108}
109
110#[derive(Debug, Clone)]
111pub struct LineSet<T> {
112    map: BTreeSet<Line<T>>,
113}
114
115impl<T> Default for LineSet<T>
116where
117    T: Ord,
118{
119    fn default() -> Self {
120        Self {
121            map: Default::default(),
122        }
123    }
124}
125
126impl<T> LineSet<T>
127where
128    T: Copy + Bounded + Ord + Add<Output = T> + Sub<Output = T> + Mul<Output = T> + Div<Output = T>,
129{
130    pub fn new() -> Self {
131        Default::default()
132    }
133    pub fn insert(&mut self, a: T, b: T) {
134        fn f<T>(la: T, lb: T, ra: T, rb: T) -> T
135        where
136            T: Copy + Ord + Sub<Output = T> + Div<Output = T>,
137        {
138            debug_assert!(la > ra);
139            (rb - lb) / (la - ra)
140        }
141        let left = self.map.range(..Slope(a)).next_back().cloned();
142        let mut right = self.map.range(Slope(a)..).next().cloned();
143        match (&left, &right) {
144            (_, Some(r)) if a == r.a.0 => {
145                if r.b <= b {
146                    return;
147                }
148                self.map.remove(r);
149                right = self.map.range(Slope(a)..).next().cloned();
150            }
151            (Some(l), Some(r)) if f(l.a.0, l.b, a, b) >= f(a, b, r.a.0, r.b) => return,
152            _ => {}
153        }
154        loop {
155            let rq = if let Some(r) = right {
156                let rq = f(a, b, r.a.0, r.b);
157                if rq >= r.q.0 {
158                    self.map.remove(&r);
159                    right = self.map.range(Slope(a)..).next().cloned();
160                    continue;
161                }
162                rq
163            } else {
164                Bounded::maximum()
165            };
166            self.map.insert(Line::new(a, b, rq));
167            break;
168        }
169        if let Some(mut l) = left {
170            self.map.remove(&l);
171            let mut lq = f(l.a.0, l.b, a, b);
172            loop {
173                if let Some(ll) = self.map.range(..Slope(a)).next_back().cloned() {
174                    self.map.remove(&ll);
175                    let llq = f(ll.a.0, ll.b, l.a.0, l.b);
176                    if llq >= lq {
177                        l = ll;
178                        lq = f(l.a.0, l.b, a, b);
179                        continue;
180                    } else {
181                        self.map.insert(Line::new(ll.a.0, ll.b, llq));
182                    }
183                };
184                break;
185            }
186            self.map.insert(Line::new(l.a.0, l.b, lq));
187        }
188    }
189    pub fn query_min(&self, x: T) -> Option<T> {
190        let Line { a, b, .. } = self.map.range(Query(x)..).next().cloned()?;
191        Some(a.0 * x + b)
192    }
193}
competitive/data_structure/line_set.rs

competitive/data_structure/
line_set.rs
