1use super::{Bounded, IntBase, RadixSortKey, SliceSortExt, Zero};
2use std::{
3 mem::swap,
4 ops::{Add, Mul, Range},
5};
6
7pub trait LiChaoLine<X>: Copy {
8 type Output: Bounded + Copy + Ord;
9
10 fn infinity() -> Self;
11 fn evaluate(&self, x: X) -> Self::Output;
12}
13
14impl<X, Y> LiChaoLine<X> for (X, Y)
15where
16 X: Copy + Into<Y> + Zero,
17 Y: Bounded + Copy + Ord + Add<Output = Y> + Mul<Output = Y>,
18{
19 type Output = Y;
20
21 fn infinity() -> Self {
22 (X::zero(), Y::maximum())
23 }
24
25 fn evaluate(&self, x: X) -> Self::Output {
26 self.0.into() * x.into() + self.1
27 }
28}
29
30enum Branch {
31 Left,
32 Right,
33}
34
35fn place_line<X, L>(
36 current: &mut L,
37 candidate: &mut L,
38 left: X,
39 middle: X,
40 right: X,
41 candidate_left: L::Output,
42 candidate_right: L::Output,
43) -> Option<(Branch, L::Output, L::Output)>
44where
45 X: Copy,
46 L: LiChaoLine<X>,
47{
48 let current_left = current.evaluate(left);
49 let current_right = current.evaluate(right);
50 if candidate_left < current_left {
51 if candidate_right < current_right {
52 swap(current, candidate);
53 return None;
54 }
55 let candidate_middle = candidate.evaluate(middle);
56 let current_middle = current.evaluate(middle);
57 if candidate_middle < current_middle {
58 swap(current, candidate);
59 Some((Branch::Right, current_middle, current_right))
60 } else {
61 Some((Branch::Left, candidate_left, candidate_middle))
62 }
63 } else if candidate_right < current_right {
64 let candidate_middle = candidate.evaluate(middle);
65 let current_middle = current.evaluate(middle);
66 if candidate_middle < current_middle {
67 swap(current, candidate);
68 Some((Branch::Left, current_left, current_middle))
69 } else {
70 Some((Branch::Right, candidate_middle, candidate_right))
71 }
72 } else {
73 None
74 }
75}
76
77#[derive(Debug, Clone)]
78struct LiChaoSegment<X, L> {
79 range: Range<X>,
80 line: L,
81}
82
83impl<X, L> LiChaoSegment<X, L>
84where
85 X: Copy + Ord,
86 L: LiChaoLine<X>,
87{
88 fn evaluate(&self, x: X) -> L::Output {
89 if self.range.contains(&x) {
90 self.line.evaluate(x)
91 } else {
92 L::infinity().evaluate(x)
93 }
94 }
95
96 fn covers(&self, left: X, right: X) -> bool {
97 self.range.start == left && self.range.end == right
98 }
99}
100
101#[derive(Debug, Clone)]
102struct LiChaoNode<X, L> {
103 segment: LiChaoSegment<X, L>,
104 children: [u32; 2],
105}
106
107#[derive(Debug, Clone)]
108pub struct LiChaoTree<X, L> {
109 range: Range<X>,
110 nodes: Vec<LiChaoNode<X, L>>,
111}
112
113impl<X, L> LiChaoTree<X, L>
114where
115 X: IntBase,
116 L: LiChaoLine<X>,
117{
118 pub fn new(range: Range<X>) -> Self {
119 assert!(range.start < range.end);
120 Self {
121 range: range.clone(),
122 nodes: vec![LiChaoNode {
123 segment: LiChaoSegment {
124 range,
125 line: L::infinity(),
126 },
127 children: [!0; 2],
128 }],
129 }
130 }
131
132 fn push_node(&mut self, segment: LiChaoSegment<X, L>) -> u32 {
133 let index = self.nodes.len() as u32;
134 self.nodes.push(LiChaoNode {
135 segment,
136 children: [!0; 2],
137 });
138 index
139 }
140
141 pub fn add_line(&mut self, line: L) {
142 self.add_segment_at(
143 0,
144 LiChaoSegment {
145 range: self.range.clone(),
146 line,
147 },
148 self.range.start,
149 self.range.end,
150 );
151 }
152
153 pub fn add_segment(&mut self, range: Range<X>, line: L) {
154 assert!(self.range.start <= range.start && range.end <= self.range.end);
155 if range.start < range.end {
156 self.add_segment_at(
157 0,
158 LiChaoSegment { range, line },
159 self.range.start,
160 self.range.end,
161 );
162 }
163 }
164
165 fn add_segment_at(
166 &mut self,
167 mut index: u32,
168 mut segment: LiChaoSegment<X, L>,
169 mut left: X,
170 mut right: X,
171 ) {
172 loop {
173 let last = right - X::one();
174 let middle = if left == last {
175 left
176 } else {
177 left.midpoint(last).min(last - X::one())
178 };
179 let split = middle + X::one();
180 if self.nodes[index as usize].segment.covers(left, right) && segment.covers(left, right)
181 {
182 let candidate_left = segment.line.evaluate(left);
183 let candidate_right = segment.line.evaluate(last);
184 let child = match place_line(
185 &mut self.nodes[index as usize].segment.line,
186 &mut segment.line,
187 left,
188 middle,
189 last,
190 candidate_left,
191 candidate_right,
192 ) {
193 None => return,
194 Some((Branch::Left, _, _)) => {
195 right = split;
196 segment.range.end = right;
197 0
198 }
199 Some((Branch::Right, _, _)) => {
200 left = split;
201 segment.range.start = left;
202 1
203 }
204 };
205 let next = self.nodes[index as usize].children[child];
206 if next == !0 {
207 let next = self.push_node(segment);
208 self.nodes[index as usize].children[child] = next;
209 return;
210 }
211 index = next;
212 continue;
213 }
214 let segment_right = segment.range.end - X::one();
215 if self.nodes[index as usize]
216 .segment
217 .evaluate(segment.range.start)
218 <= segment.line.evaluate(segment.range.start)
219 && self.nodes[index as usize].segment.evaluate(segment_right)
220 <= segment.line.evaluate(segment_right)
221 {
222 return;
223 }
224 let current = &self.nodes[index as usize].segment;
225 let current_left = current.range.start;
226 let current_right = current.range.end - X::one();
227 if current.line.evaluate(current_left) >= segment.evaluate(current_left)
228 && current.line.evaluate(current_right) >= segment.evaluate(current_right)
229 {
230 self.nodes[index as usize].segment = segment;
231 return;
232 }
233 if segment.covers(left, right) {
234 swap(&mut self.nodes[index as usize].segment, &mut segment);
235 }
236 let child;
237 if segment.range.end <= split {
238 child = 0;
239 right = split;
240 } else if middle < segment.range.start {
241 child = 1;
242 left = split;
243 } else {
244 let right_segment = LiChaoSegment {
245 range: split..segment.range.end,
246 line: segment.line,
247 };
248 segment.range.end = split;
249 let next = self.nodes[index as usize].children[0];
250 if next == !0 {
251 let next = self.push_node(segment);
252 self.nodes[index as usize].children[0] = next;
253 } else {
254 self.add_segment_at(next, segment, left, split);
255 }
256 let next = self.nodes[index as usize].children[1];
257 if next == !0 {
258 let next = self.push_node(right_segment);
259 self.nodes[index as usize].children[1] = next;
260 } else {
261 self.add_segment_at(next, right_segment, split, right);
262 }
263 return;
264 }
265 let next = self.nodes[index as usize].children[child];
266 if next == !0 {
267 let next = self.push_node(segment);
268 self.nodes[index as usize].children[child] = next;
269 return;
270 }
271 index = next;
272 }
273 }
274
275 pub fn query_min(&self, x: X) -> Option<L::Output> {
276 assert!(self.range.contains(&x));
277 let infinity = L::infinity().evaluate(x);
278 let mut result = infinity;
279 let (mut index, mut left, mut right) = (0, self.range.start, self.range.end);
280 while index != !0 {
281 let node = &self.nodes[index as usize];
282 result = result.min(node.segment.evaluate(x));
283 let last = right - X::one();
284 let middle = if left == last {
285 left
286 } else {
287 left.midpoint(last).min(last - X::one())
288 };
289 let split = middle + X::one();
290 if x <= middle {
291 index = node.children[0];
292 right = split;
293 } else {
294 index = node.children[1];
295 left = split;
296 }
297 }
298 (result != infinity).then_some(result)
299 }
300}
301
302#[derive(Debug, Clone, Copy)]
303enum LiChaoEvent<X, L> {
304 Line(L),
305 Segment(X, X, L),
306 Query(X, u32),
307}
308
309#[derive(Debug, Clone)]
310pub struct OfflineLiChaoTree<X, L> {
311 events: Vec<LiChaoEvent<X, L>>,
312 queries: usize,
313}
314
315impl<X, L> Default for OfflineLiChaoTree<X, L> {
316 fn default() -> Self {
317 Self {
318 events: Vec::new(),
319 queries: 0,
320 }
321 }
322}
323
324impl<X, L> OfflineLiChaoTree<X, L>
325where
326 X: Copy + Ord + RadixSortKey,
327 L: LiChaoLine<X>,
328{
329 pub fn new() -> Self {
330 Self::default()
331 }
332
333 pub fn add_line(&mut self, line: L) {
334 self.events.push(LiChaoEvent::Line(line));
335 }
336
337 pub fn add_segment(&mut self, range: Range<X>, line: L) {
338 self.events
339 .push(LiChaoEvent::Segment(range.start, range.end, line));
340 }
341
342 pub fn query_min(&mut self, x: X) -> usize {
343 let index = self.queries;
344 self.events.push(LiChaoEvent::Query(x, index as u32));
345 self.queries += 1;
346 index
347 }
348
349 pub fn execute(self) -> Vec<Option<L::Output>> {
350 let mut markers = Vec::with_capacity(2 * self.events.len());
351 for (i, event) in self.events.iter().enumerate() {
352 let i = i as u32;
353 match *event {
354 LiChaoEvent::Line(_) => {}
355 LiChaoEvent::Segment(left, right, _) => {
356 markers.push((left, i << 2));
357 markers.push((right, i << 2 | 1));
358 }
359 LiChaoEvent::Query(x, _) => markers.push((x, i << 2 | 2)),
360 }
361 }
362 markers.radix_sort_by_key(|&(x, _)| x);
363
364 let mut positions = vec![[0u32; 2]; self.events.len()];
365 let mut coordinates = Vec::with_capacity(self.queries);
366 let mut left = 0;
367 while left < markers.len() {
368 let x = markers[left].0;
369 let mut right = left + 1;
370 while right < markers.len() && markers[right].0 == x {
371 right += 1;
372 }
373 let index = coordinates.len() as u32;
374 let mut queried = false;
375 for &(_, marker) in &markers[left..right] {
376 let event = (marker >> 2) as usize;
377 match marker & 3 {
378 0 => positions[event][0] = index,
379 1 => positions[event][1] = index,
380 _ => {
381 positions[event][0] = index;
382 queried = true;
383 }
384 }
385 }
386 if queried {
387 coordinates.push(x);
388 }
389 left = right;
390 }
391 if let Some(&x) = coordinates.last() {
392 coordinates.resize(coordinates.len().next_power_of_two(), x);
393 coordinates.push(x);
394 }
395
396 let mut tree = IndexedLiChaoTree::new(&coordinates);
397 let mut result = vec![None; self.queries];
398 for (i, event) in self.events.into_iter().enumerate() {
399 match event {
400 LiChaoEvent::Line(line) => tree.add_line(line),
401 LiChaoEvent::Segment(_, _, line) => {
402 let [left, right] = positions[i];
403 tree.add_segment(left as usize..right as usize, line);
404 }
405 LiChaoEvent::Query(_, output) => {
406 result[output as usize] = tree.query_min(positions[i][0] as usize);
407 }
408 }
409 }
410 result
411 }
412}
413
414struct IndexedLiChaoTree<'a, X, L>
415where
416 L: LiChaoLine<X>,
417{
418 size: usize,
419 coordinates: &'a [X],
420 lines: Vec<L>,
421}
422
423impl<X, L> IndexedLiChaoTree<'_, X, L>
424where
425 X: Copy,
426 L: LiChaoLine<X>,
427{
428 fn new(coordinates: &[X]) -> IndexedLiChaoTree<'_, X, L> {
429 let size = coordinates.len().saturating_sub(1);
430 IndexedLiChaoTree {
431 size,
432 coordinates,
433 lines: vec![L::infinity(); 2 * size],
434 }
435 }
436
437 fn add_line(&mut self, line: L) {
438 if self.size != 0 {
439 self.add_line_at(1, self.size.trailing_zeros() as usize, line);
440 }
441 }
442
443 fn add_line_at(&mut self, mut index: usize, height: usize, mut line: L) {
444 let mut left = (index << height) - self.size;
445 let mut right = left + (1 << height);
446 let mut values = (
447 line.evaluate(self.coordinates[left]),
448 line.evaluate(self.coordinates[right]),
449 );
450 loop {
451 if left + 1 == right {
452 if values.0 < self.lines[index].evaluate(self.coordinates[left]) {
453 self.lines[index] = line;
454 }
455 return;
456 }
457 let middle = (left + right) / 2;
458 match place_line(
459 &mut self.lines[index],
460 &mut line,
461 self.coordinates[left],
462 self.coordinates[middle],
463 self.coordinates[right],
464 values.0,
465 values.1,
466 ) {
467 None => return,
468 Some((Branch::Left, left_value, right_value)) => {
469 index *= 2;
470 right = middle;
471 values = (left_value, right_value);
472 }
473 Some((Branch::Right, left_value, right_value)) => {
474 index = 2 * index + 1;
475 left = middle;
476 values = (left_value, right_value);
477 }
478 }
479 }
480 }
481
482 fn add_segment(&mut self, range: Range<usize>, line: L) {
483 let n = self.size;
484 if range.start == range.end {
485 return;
486 }
487 let mut left = n + range.start - 1;
488 let mut right = n + range.end;
489 let width = (left ^ right).ilog2();
490 let mask = (1usize << width) - 1;
491 let fixed = left;
492 left = !left & mask;
493 while left != 0 {
494 let height = left.trailing_zeros();
495 left &= left - 1;
496 self.add_line_at((fixed >> height) ^ 1, height as usize, line);
497 }
498 let fixed = right;
499 right &= mask;
500 while right != 0 {
501 let height = right.trailing_zeros();
502 right &= right - 1;
503 self.add_line_at((fixed >> height) ^ 1, height as usize, line);
504 }
505 }
506
507 fn query_min(&self, index: usize) -> Option<L::Output> {
508 let x = self.coordinates[index];
509 let infinity = L::infinity().evaluate(x);
510 let mut result = infinity;
511 let mut index = self.size + index;
512 while index != 0 {
513 result = result.min(self.lines[index].evaluate(x));
514 index >>= 1;
515 }
516 (result != infinity).then_some(result)
517 }
518}
519
520#[cfg(test)]
521mod tests {
522 use super::*;
523 use crate::{rand, tools::Xorshift};
524
525 #[test]
526 fn test_li_chao_tree() {
527 let mut rng = Xorshift::default();
528 for _ in 0..100 {
529 let mut online: LiChaoTree<i32, (i32, i64)> = LiChaoTree::new(-21..22);
530 let mut offline: OfflineLiChaoTree<i32, (i32, i64)> = OfflineLiChaoTree::new();
531 let mut lines = Vec::new();
532 let mut expected = Vec::new();
533 for _ in 0..200 {
534 rand!(rng, ty: 0..3, mut l: -20..=20, mut r: -20..=20, a: -20..=20, b: -100..=100, x: -20..=20);
535 if l > r {
536 swap(&mut l, &mut r);
537 }
538 match ty {
539 0 => {
540 online.add_line((a, b));
541 offline.add_line((a, b));
542 lines.push((-21..22, a, b));
543 }
544 1 => {
545 online.add_segment(l..r, (a, b));
546 offline.add_segment(l..r, (a, b));
547 lines.push((l..r, a, b));
548 }
549 _ => {
550 let result = lines
551 .iter()
552 .filter(|(range, _, _)| range.contains(&x))
553 .map(|(_, a, b)| i64::from(*a) * i64::from(x) + b)
554 .min();
555 assert_eq!(online.query_min(x), result);
556 offline.query_min(x);
557 expected.push(result);
558 }
559 }
560 }
561 assert_eq!(offline.execute(), expected);
562 }
563 }
564}