fn place_line<X, L>(
current: &mut L,
candidate: &mut L,
left: X,
middle: X,
right: X,
candidate_left: L::Output,
candidate_right: L::Output,
) -> Option<(Branch, L::Output, L::Output)>where
X: Copy,
L: LiChaoLine<X>,Examples found in repository?
crates/competitive/src/data_structure/li_chao_tree.rs (lines 184-192)
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 }