Struct LiChaoSegment 

struct LiChaoSegment<X, L> {
    range: Range<X>,
    line: L,
}

Fields

range: Range<X>

line: L

Implementations

impl<X, L> LiChaoSegment<X, L>

where X: Copy + Ord, L: LiChaoLine<X>,

fn evaluate(&self, x: X) -> L::Output

Examples found in repository

crates/competitive/src/data_structure/li_chao_tree.rs (line 217)

    fn add_segment_at(
        &mut self,
        mut index: u32,
        mut segment: LiChaoSegment<X, L>,
        mut left: X,
        mut right: X,
    ) {
        loop {
            let last = right - X::one();
            let middle = if left == last {
                left
            } else {
                left.midpoint(last).min(last - X::one())
            };
            let split = middle + X::one();
            if self.nodes[index as usize].segment.covers(left, right) && segment.covers(left, right)
            {
                let candidate_left = segment.line.evaluate(left);
                let candidate_right = segment.line.evaluate(last);
                let child = match place_line(
                    &mut self.nodes[index as usize].segment.line,
                    &mut segment.line,
                    left,
                    middle,
                    last,
                    candidate_left,
                    candidate_right,
                ) {
                    None => return,
                    Some((Branch::Left, _, _)) => {
                        right = split;
                        segment.range.end = right;
                        0
                    }
                    Some((Branch::Right, _, _)) => {
                        left = split;
                        segment.range.start = left;
                        1
                    }
                };
                let next = self.nodes[index as usize].children[child];
                if next == !0 {
                    let next = self.push_node(segment);
                    self.nodes[index as usize].children[child] = next;
                    return;
                }
                index = next;
                continue;
            }
            let segment_right = segment.range.end - X::one();
            if self.nodes[index as usize]
                .segment
                .evaluate(segment.range.start)
                <= segment.line.evaluate(segment.range.start)
                && self.nodes[index as usize].segment.evaluate(segment_right)
                    <= segment.line.evaluate(segment_right)
            {
                return;
            }
            let current = &self.nodes[index as usize].segment;
            let current_left = current.range.start;
            let current_right = current.range.end - X::one();
            if current.line.evaluate(current_left) >= segment.evaluate(current_left)
                && current.line.evaluate(current_right) >= segment.evaluate(current_right)
            {
                self.nodes[index as usize].segment = segment;
                return;
            }
            if segment.covers(left, right) {
                swap(&mut self.nodes[index as usize].segment, &mut segment);
            }
            let child;
            if segment.range.end <= split {
                child = 0;
                right = split;
            } else if middle < segment.range.start {
                child = 1;
                left = split;
            } else {
                let right_segment = LiChaoSegment {
                    range: split..segment.range.end,
                    line: segment.line,
                };
                segment.range.end = split;
                let next = self.nodes[index as usize].children[0];
                if next == !0 {
                    let next = self.push_node(segment);
                    self.nodes[index as usize].children[0] = next;
                } else {
                    self.add_segment_at(next, segment, left, split);
                }
                let next = self.nodes[index as usize].children[1];
                if next == !0 {
                    let next = self.push_node(right_segment);
                    self.nodes[index as usize].children[1] = next;
                } else {
                    self.add_segment_at(next, right_segment, split, right);
                }
                return;
            }
            let next = self.nodes[index as usize].children[child];
            if next == !0 {
                let next = self.push_node(segment);
                self.nodes[index as usize].children[child] = next;
                return;
            }
            index = next;
        }
    }

    pub fn query_min(&self, x: X) -> Option<L::Output> {
        assert!(self.range.contains(&x));
        let infinity = L::infinity().evaluate(x);
        let mut result = infinity;
        let (mut index, mut left, mut right) = (0, self.range.start, self.range.end);
        while index != !0 {
            let node = &self.nodes[index as usize];
            result = result.min(node.segment.evaluate(x));
            let last = right - X::one();
            let middle = if left == last {
                left
            } else {
                left.midpoint(last).min(last - X::one())
            };
            let split = middle + X::one();
            if x <= middle {
                index = node.children[0];
                right = split;
            } else {
                index = node.children[1];
                left = split;
            }
        }
        (result != infinity).then_some(result)
    }

fn covers(&self, left: X, right: X) -> bool

Examples found in repository

crates/competitive/src/data_structure/li_chao_tree.rs (line 180)

    fn add_segment_at(
        &mut self,
        mut index: u32,
        mut segment: LiChaoSegment<X, L>,
        mut left: X,
        mut right: X,
    ) {
        loop {
            let last = right - X::one();
            let middle = if left == last {
                left
            } else {
                left.midpoint(last).min(last - X::one())
            };
            let split = middle + X::one();
            if self.nodes[index as usize].segment.covers(left, right) && segment.covers(left, right)
            {
                let candidate_left = segment.line.evaluate(left);
                let candidate_right = segment.line.evaluate(last);
                let child = match place_line(
                    &mut self.nodes[index as usize].segment.line,
                    &mut segment.line,
                    left,
                    middle,
                    last,
                    candidate_left,
                    candidate_right,
                ) {
                    None => return,
                    Some((Branch::Left, _, _)) => {
                        right = split;
                        segment.range.end = right;
                        0
                    }
                    Some((Branch::Right, _, _)) => {
                        left = split;
                        segment.range.start = left;
                        1
                    }
                };
                let next = self.nodes[index as usize].children[child];
                if next == !0 {
                    let next = self.push_node(segment);
                    self.nodes[index as usize].children[child] = next;
                    return;
                }
                index = next;
                continue;
            }
            let segment_right = segment.range.end - X::one();
            if self.nodes[index as usize]
                .segment
                .evaluate(segment.range.start)
                <= segment.line.evaluate(segment.range.start)
                && self.nodes[index as usize].segment.evaluate(segment_right)
                    <= segment.line.evaluate(segment_right)
            {
                return;
            }
            let current = &self.nodes[index as usize].segment;
            let current_left = current.range.start;
            let current_right = current.range.end - X::one();
            if current.line.evaluate(current_left) >= segment.evaluate(current_left)
                && current.line.evaluate(current_right) >= segment.evaluate(current_right)
            {
                self.nodes[index as usize].segment = segment;
                return;
            }
            if segment.covers(left, right) {
                swap(&mut self.nodes[index as usize].segment, &mut segment);
            }
            let child;
            if segment.range.end <= split {
                child = 0;
                right = split;
            } else if middle < segment.range.start {
                child = 1;
                left = split;
            } else {
                let right_segment = LiChaoSegment {
                    range: split..segment.range.end,
                    line: segment.line,
                };
                segment.range.end = split;
                let next = self.nodes[index as usize].children[0];
                if next == !0 {
                    let next = self.push_node(segment);
                    self.nodes[index as usize].children[0] = next;
                } else {
                    self.add_segment_at(next, segment, left, split);
                }
                let next = self.nodes[index as usize].children[1];
                if next == !0 {
                    let next = self.push_node(right_segment);
                    self.nodes[index as usize].children[1] = next;
                } else {
                    self.add_segment_at(next, right_segment, split, right);
                }
                return;
            }
            let next = self.nodes[index as usize].children[child];
            if next == !0 {
                let next = self.push_node(segment);
                self.nodes[index as usize].children[child] = next;
                return;
            }
            index = next;
        }
    }

Trait Implementations

impl<X: Clone, L: Clone> Clone for LiChaoSegment<X, L>

fn clone(&self) -> Self

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<X: Debug, L: Debug> Debug for LiChaoSegment<X, L>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.