nekolib/math/slope_function.rs
1//! 区分線形凸関数。
2
3use std::cmp::Reverse;
4use std::collections::BinaryHeap;
5use std::fmt::Debug;
6use std::ops::{Add, AddAssign, Bound, RangeInclusive};
7
8/// 区分線形凸関数。
9///
10/// 整数の多重集合 $L$, $R$ に対して、次の形で表せる関数を管理する：
11/// $$ f(x) = c + \\sum\_{l\\in L} (l-x)\_+ + \\sum\_{r\\in R} (x-r)\_+. $$
12/// ここで、$(a-x)\_+ = \\max\\{0, a-x\\}$、$(x-a)\_+ = \\max\\{0, x-a\\}$ とする。
13/// たとえば、$|x-a| = (a-x)\_+ + (x-a)\_+$ と書ける。
14///
15/// # Idea
16/// `todo!()`
17///
18/// # Complexity
19/// |演算|時間計算量|
20/// |---|---|
21/// |`new`|$O(1)$|
22/// |`add_const`|$O(1)$|
23/// |`add_left`, `add_right`, `add_abs`|$O(\\log(\|L\|) + \\log(\|R\|))$|
24/// |`min_left`, `min_right`|amortized $O(1)$|
25/// |`shift`, `window`|$O(1)$|
26/// |`min`, `argmin`|$O(1)$|
27///
28/// # Examples
29/// ```
30/// use std::ops::Bound::{Included, Unbounded};
31///
32/// use nekolib::math::SlopeFunction;
33///
34/// let mut sf = SlopeFunction::new();
35/// sf.add_left(-1);
36/// sf.add_left(3);
37/// sf.add_right(2);
38/// sf.add_const(-10);
39/// // f(x) = 0.max(-1-x) + 0.max(3-x) + 0.max(x-2) - 10
40/// // x | -5 -4 -3 -2 -1 0 1 2 3 4 5
41/// // f(x) | 2 0 -2 -4 -6 -7 -8 -9 -9 -8 -7
42/// assert_eq!(sf.min(), -9);
43/// assert_eq!(sf.argmin(), (Included(2), Included(3)));
44/// ```
45///
46/// # Notes
47/// $(a\_1, a\_2, \\dots, a\_n)$ の中央値を $a\_{\\text{med}}$ とすると、
48/// $\\sum\_{i=1}^n |x-a\_i|$ は $x = a\_{\\text{med}}$ のとき最小となる。
49/// このことから、値の追加と中央値を求めるクエリを処理できる。
50///
51/// ```
52/// use std::ops::Bound::{Included, Excluded, Unbounded};
53///
54/// use nekolib::math::SlopeFunction;
55///
56/// #[derive(Clone, Default)]
57/// struct IncrementalMedian(SlopeFunction<i32>);
58///
59/// impl IncrementalMedian {
60/// fn new() -> Self { Self::default() }
61/// fn insert(&mut self, a: i32) { self.0.add_abs(a); }
62/// fn median(&self) -> Option<i32> {
63/// match self.0.argmin().0 {
64/// Included(x) => Some(x),
65/// Excluded(_) => unreachable!(),
66/// Unbounded => None,
67/// }
68/// }
69/// }
70///
71/// let mut im = IncrementalMedian::new();
72/// assert_eq!(im.median(), None); // {{}}
73/// im.insert(2);
74/// assert_eq!(im.median(), Some(2)); // {{2}}
75/// im.insert(3);
76/// assert_eq!(im.median(), Some(2)); // {{2, 3}}
77/// im.insert(1);
78/// assert_eq!(im.median(), Some(2)); // {{1, 2, 3}}
79/// im.insert(1);
80/// assert_eq!(im.median(), Some(1)); // {{1, 1, 2, 3}}
81/// ```
82///
83/// # References
84/// - <https://maspypy.com/slope-trick-1-%E8%A7%A3%E8%AA%AC%E7%B7%A8>
85#[derive(Clone, Debug, Default)]
86pub struct SlopeFunction<I: Ord> {
87 left: BinaryHeap<I>,
88 right: BinaryHeap<Reverse<I>>,
89 min: I,
90 shl: I,
91 shr: I,
92}
93
94impl<I: SlopeTrickInt> SlopeFunction<I> {
95 /// $f(x) = 0$ で初期化する。
96 ///
97 /// # Examples
98 /// ```
99 /// use std::ops::Bound::Unbounded;
100 ///
101 /// use nekolib::math::SlopeFunction;
102 ///
103 /// let sf = SlopeFunction::<i32>::new();
104 /// assert_eq!(sf.min(), 0);
105 /// assert_eq!(sf.argmin(), (Unbounded, Unbounded));
106 /// ```
107 pub fn new() -> Self { Self::default() }
108 /// $f(x) \\xleftarrow{+} c$ で更新する。
109 ///
110 /// # Examples
111 /// ```
112 /// use nekolib::math::SlopeFunction;
113 ///
114 /// let mut sf = SlopeFunction::new();
115 /// assert_eq!(sf.min(), 0);
116 /// sf.add_const(3);
117 /// assert_eq!(sf.min(), 3);
118 /// sf.add_const(-1);
119 /// assert_eq!(sf.min(), 2);
120 /// ```
121 pub fn add_const(&mut self, c: I) { self.min += c; }
122 /// $f(x) \\xleftarrow{+} (l-x)\_+$ で更新する。
123 ///
124 /// # Examples
125 /// ```
126 /// use std::ops::Bound::{Included, Unbounded};
127 ///
128 /// use nekolib::math::SlopeFunction;
129 ///
130 /// let mut sf = SlopeFunction::new();
131 /// sf.add_left(4);
132 /// assert_eq!(sf.argmin(), (Included(4), Unbounded));
133 /// ```
134 pub fn add_left(&mut self, l: I) {
135 if self.right.is_empty() {
136 self.left.push(l);
137 return;
138 }
139 self.min += l.doz(self.right.peek().unwrap().0);
140 self.right.push(Reverse(l));
141 let l = self.right.pop().unwrap().0;
142 self.left.push(l);
143 }
144 /// $f(x) \\xleftarrow{+} (x-r)\_+$ で更新する。
145 ///
146 /// # Examples
147 /// ```
148 /// use std::ops::Bound::{Included, Unbounded};
149 ///
150 /// use nekolib::math::SlopeFunction;
151 ///
152 /// let mut sf = SlopeFunction::new();
153 /// sf.add_right(4);
154 /// assert_eq!(sf.argmin(), (Unbounded, Included(4)));
155 /// ```
156 pub fn add_right(&mut self, r: I) {
157 if self.left.is_empty() {
158 self.right.push(Reverse(r));
159 return;
160 }
161 self.min += self.left.peek().unwrap().doz(r);
162 self.left.push(r);
163 let r = self.left.pop().unwrap();
164 self.right.push(Reverse(r));
165 }
166 /// $f(x) \\xleftarrow{+} |x-a|$ で更新する。
167 ///
168 /// # Examples
169 /// ```
170 /// use std::ops::Bound::Included;
171 ///
172 /// use nekolib::math::SlopeFunction;
173 ///
174 /// let mut sf = SlopeFunction::new();
175 /// sf.add_abs(4);
176 /// assert_eq!(sf.argmin(), (Included(4), Included(4)));
177 /// ```
178 pub fn add_abs(&mut self, a: I) {
179 self.add_left(a);
180 self.add_right(a);
181 }
182 /// $g(x) = \\min\_{y\\le x} f(y)$ として、$f\\gets g$ で更新する。
183 ///
184 /// # Examples
185 /// ```
186 /// use std::ops::Bound::{Included, Unbounded};
187 ///
188 /// use nekolib::math::SlopeFunction;
189 ///
190 /// let mut sf = SlopeFunction::new();
191 /// sf.add_abs(4);
192 /// assert_eq!(sf.argmin(), (Included(4), Included(4)));
193 /// sf.min_left();
194 /// assert_eq!(sf.argmin(), (Included(4), Unbounded));
195 /// ```
196 pub fn min_left(&mut self) { self.right.clear(); }
197 /// $g(x) = \\min\_{y\\ge x} f(y)$ として、$f\\gets g$ で更新する。
198 ///
199 /// # Examples
200 /// ```
201 /// use std::ops::Bound::{Included, Unbounded};
202 ///
203 /// use nekolib::math::SlopeFunction;
204 ///
205 /// let mut sf = SlopeFunction::new();
206 /// sf.add_abs(4);
207 /// assert_eq!(sf.argmin(), (Included(4), Included(4)));
208 /// sf.min_right();
209 /// assert_eq!(sf.argmin(), (Unbounded, Included(4)));
210 /// ```
211 pub fn min_right(&mut self) { self.left.clear(); }
212 /// $g(x) = f(x-a)$ として、$f\\gets g$ で更新する。
213 ///
214 /// # Examples
215 /// ```
216 /// use std::ops::Bound::Included;
217 ///
218 /// use nekolib::math::SlopeFunction;
219 ///
220 /// let mut sf = SlopeFunction::new();
221 /// sf.add_abs(4);
222 /// assert_eq!(sf.argmin(), (Included(4), Included(4)));
223 /// sf.shift(2);
224 /// assert_eq!(sf.argmin(), (Included(6), Included(6)));
225 /// ```
226 pub fn shift(&mut self, s: I) {
227 self.shl += s;
228 self.shr += s;
229 }
230 /// $[a, b]$ に対して $g(x) = \\min\_{y\\in[x-b, x-a]} f(y)$ として、$f\\gets g$ で更新する。
231 ///
232 /// # Examples
233 /// ```
234 /// use std::ops::Bound::Included;
235 ///
236 /// use nekolib::math::SlopeFunction;
237 ///
238 /// let mut sf = SlopeFunction::new();
239 /// sf.add_abs(4);
240 /// assert_eq!(sf.argmin(), (Included(4), Included(4)));
241 /// sf.window(-1..=2);
242 /// assert_eq!(sf.argmin(), (Included(3), Included(6)));
243 /// ```
244 pub fn window(&mut self, window: RangeInclusive<I>) {
245 self.shl += *window.start();
246 self.shr += *window.end();
247 }
248 /// $\\min\_{x\\in\\mathbb{R}} f(x)$ を返す。
249 ///
250 /// # Examples
251 /// ```
252 /// use nekolib::math::SlopeFunction;
253 ///
254 /// let mut sf = SlopeFunction::new();
255 /// sf.add_abs(4);
256 /// sf.add_const(1);
257 /// assert_eq!(sf.min(), 1);
258 /// ```
259 pub fn min(&self) -> I { self.min }
260 /// $\\argmin\_{x\\in\\mathbb{R}} f(x)$ を返す。
261 ///
262 /// # Examples
263 /// ```
264 /// use std::ops::Bound::Included;
265 /// use nekolib::math::SlopeFunction;
266 ///
267 /// let mut sf = SlopeFunction::new();
268 /// sf.add_abs(4);
269 /// sf.add_const(1);
270 /// assert_eq!(sf.argmin(), (Included(4), Included(4)));
271 /// ```
272 pub fn argmin(&self) -> (Bound<I>, Bound<I>) {
273 let left = match self.left.peek() {
274 Some(&x) => Bound::Included(x + self.shl),
275 None => Bound::Unbounded,
276 };
277 let right = match self.right.peek() {
278 Some(&Reverse(x)) => Bound::Included(x + self.shr),
279 None => Bound::Unbounded,
280 };
281 (left, right)
282 }
283}
284
285pub trait SlopeTrickInt:
286 Copy + Add<Output = Self> + AddAssign + Default + Ord
287{
288 // unsigned でいうところの saturating_sub
289 fn doz(self, rhs: Self) -> Self;
290}
291
292macro_rules! impl_slope_trick_int {
293 ( $($ty:tt)* ) => { $(
294 impl SlopeTrickInt for $ty {
295 fn doz(self, rhs: Self) -> Self {
296 0.max(self - rhs)
297 }
298 }
299 )* }
300}
301
302impl_slope_trick_int! { i8 i16 i32 i64 i128 isize }