Struct IndexedLiChaoTree 

struct IndexedLiChaoTree<'a, X, L>
where
    L: LiChaoLine<X>,
{
    size: usize,
    coordinates: &'a [X],
    lines: Vec<L>,
}

Fields

size: usize

coordinates: &'a [X]

lines: Vec<L>

Implementations

impl<X, L> IndexedLiChaoTree<'_, X, L>

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

fn new(coordinates: &[X]) -> IndexedLiChaoTree<'_, X, L>

Examples found in repository

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

    pub fn execute(self) -> Vec<Option<L::Output>> {
        let mut markers = Vec::with_capacity(2 * self.events.len());
        for (i, event) in self.events.iter().enumerate() {
            let i = i as u32;
            match *event {
                LiChaoEvent::Line(_) => {}
                LiChaoEvent::Segment(left, right, _) => {
                    markers.push((left, i << 2));
                    markers.push((right, i << 2 | 1));
                }
                LiChaoEvent::Query(x, _) => markers.push((x, i << 2 | 2)),
            }
        }
        markers.radix_sort_by_key(|&(x, _)| x);

        let mut positions = vec![[0u32; 2]; self.events.len()];
        let mut coordinates = Vec::with_capacity(self.queries);
        let mut left = 0;
        while left < markers.len() {
            let x = markers[left].0;
            let mut right = left + 1;
            while right < markers.len() && markers[right].0 == x {
                right += 1;
            }
            let index = coordinates.len() as u32;
            let mut queried = false;
            for &(_, marker) in &markers[left..right] {
                let event = (marker >> 2) as usize;
                match marker & 3 {
                    0 => positions[event][0] = index,
                    1 => positions[event][1] = index,
                    _ => {
                        positions[event][0] = index;
                        queried = true;
                    }
                }
            }
            if queried {
                coordinates.push(x);
            }
            left = right;
        }
        if let Some(&x) = coordinates.last() {
            coordinates.resize(coordinates.len().next_power_of_two(), x);
            coordinates.push(x);
        }

        let mut tree = IndexedLiChaoTree::new(&coordinates);
        let mut result = vec![None; self.queries];
        for (i, event) in self.events.into_iter().enumerate() {
            match event {
                LiChaoEvent::Line(line) => tree.add_line(line),
                LiChaoEvent::Segment(_, _, line) => {
                    let [left, right] = positions[i];
                    tree.add_segment(left as usize..right as usize, line);
                }
                LiChaoEvent::Query(_, output) => {
                    result[output as usize] = tree.query_min(positions[i][0] as usize);
                }
            }
        }
        result
    }

fn add_line(&mut self, line: L)

Examples found in repository

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

    pub fn execute(self) -> Vec<Option<L::Output>> {
        let mut markers = Vec::with_capacity(2 * self.events.len());
        for (i, event) in self.events.iter().enumerate() {
            let i = i as u32;
            match *event {
                LiChaoEvent::Line(_) => {}
                LiChaoEvent::Segment(left, right, _) => {
                    markers.push((left, i << 2));
                    markers.push((right, i << 2 | 1));
                }
                LiChaoEvent::Query(x, _) => markers.push((x, i << 2 | 2)),
            }
        }
        markers.radix_sort_by_key(|&(x, _)| x);

        let mut positions = vec![[0u32; 2]; self.events.len()];
        let mut coordinates = Vec::with_capacity(self.queries);
        let mut left = 0;
        while left < markers.len() {
            let x = markers[left].0;
            let mut right = left + 1;
            while right < markers.len() && markers[right].0 == x {
                right += 1;
            }
            let index = coordinates.len() as u32;
            let mut queried = false;
            for &(_, marker) in &markers[left..right] {
                let event = (marker >> 2) as usize;
                match marker & 3 {
                    0 => positions[event][0] = index,
                    1 => positions[event][1] = index,
                    _ => {
                        positions[event][0] = index;
                        queried = true;
                    }
                }
            }
            if queried {
                coordinates.push(x);
            }
            left = right;
        }
        if let Some(&x) = coordinates.last() {
            coordinates.resize(coordinates.len().next_power_of_two(), x);
            coordinates.push(x);
        }

        let mut tree = IndexedLiChaoTree::new(&coordinates);
        let mut result = vec![None; self.queries];
        for (i, event) in self.events.into_iter().enumerate() {
            match event {
                LiChaoEvent::Line(line) => tree.add_line(line),
                LiChaoEvent::Segment(_, _, line) => {
                    let [left, right] = positions[i];
                    tree.add_segment(left as usize..right as usize, line);
                }
                LiChaoEvent::Query(_, output) => {
                    result[output as usize] = tree.query_min(positions[i][0] as usize);
                }
            }
        }
        result
    }

fn add_line_at(&mut self, index: usize, height: usize, line: L)

Examples found in repository

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

    fn add_line(&mut self, line: L) {
        if self.size != 0 {
            self.add_line_at(1, self.size.trailing_zeros() as usize, line);
        }
    }

    fn add_line_at(&mut self, mut index: usize, height: usize, mut line: L) {
        let mut left = (index << height) - self.size;
        let mut right = left + (1 << height);
        let mut values = (
            line.evaluate(self.coordinates[left]),
            line.evaluate(self.coordinates[right]),
        );
        loop {
            if left + 1 == right {
                if values.0 < self.lines[index].evaluate(self.coordinates[left]) {
                    self.lines[index] = line;
                }
                return;
            }
            let middle = (left + right) / 2;
            match place_line(
                &mut self.lines[index],
                &mut line,
                self.coordinates[left],
                self.coordinates[middle],
                self.coordinates[right],
                values.0,
                values.1,
            ) {
                None => return,
                Some((Branch::Left, left_value, right_value)) => {
                    index *= 2;
                    right = middle;
                    values = (left_value, right_value);
                }
                Some((Branch::Right, left_value, right_value)) => {
                    index = 2 * index + 1;
                    left = middle;
                    values = (left_value, right_value);
                }
            }
        }
    }

    fn add_segment(&mut self, range: Range<usize>, line: L) {
        let n = self.size;
        if range.start == range.end {
            return;
        }
        let mut left = n + range.start - 1;
        let mut right = n + range.end;
        let width = (left ^ right).ilog2();
        let mask = (1usize << width) - 1;
        let fixed = left;
        left = !left & mask;
        while left != 0 {
            let height = left.trailing_zeros();
            left &= left - 1;
            self.add_line_at((fixed >> height) ^ 1, height as usize, line);
        }
        let fixed = right;
        right &= mask;
        while right != 0 {
            let height = right.trailing_zeros();
            right &= right - 1;
            self.add_line_at((fixed >> height) ^ 1, height as usize, line);
        }
    }

fn add_segment(&mut self, range: Range<usize>, line: L)

Examples found in repository

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

    pub fn execute(self) -> Vec<Option<L::Output>> {
        let mut markers = Vec::with_capacity(2 * self.events.len());
        for (i, event) in self.events.iter().enumerate() {
            let i = i as u32;
            match *event {
                LiChaoEvent::Line(_) => {}
                LiChaoEvent::Segment(left, right, _) => {
                    markers.push((left, i << 2));
                    markers.push((right, i << 2 | 1));
                }
                LiChaoEvent::Query(x, _) => markers.push((x, i << 2 | 2)),
            }
        }
        markers.radix_sort_by_key(|&(x, _)| x);

        let mut positions = vec![[0u32; 2]; self.events.len()];
        let mut coordinates = Vec::with_capacity(self.queries);
        let mut left = 0;
        while left < markers.len() {
            let x = markers[left].0;
            let mut right = left + 1;
            while right < markers.len() && markers[right].0 == x {
                right += 1;
            }
            let index = coordinates.len() as u32;
            let mut queried = false;
            for &(_, marker) in &markers[left..right] {
                let event = (marker >> 2) as usize;
                match marker & 3 {
                    0 => positions[event][0] = index,
                    1 => positions[event][1] = index,
                    _ => {
                        positions[event][0] = index;
                        queried = true;
                    }
                }
            }
            if queried {
                coordinates.push(x);
            }
            left = right;
        }
        if let Some(&x) = coordinates.last() {
            coordinates.resize(coordinates.len().next_power_of_two(), x);
            coordinates.push(x);
        }

        let mut tree = IndexedLiChaoTree::new(&coordinates);
        let mut result = vec![None; self.queries];
        for (i, event) in self.events.into_iter().enumerate() {
            match event {
                LiChaoEvent::Line(line) => tree.add_line(line),
                LiChaoEvent::Segment(_, _, line) => {
                    let [left, right] = positions[i];
                    tree.add_segment(left as usize..right as usize, line);
                }
                LiChaoEvent::Query(_, output) => {
                    result[output as usize] = tree.query_min(positions[i][0] as usize);
                }
            }
        }
        result
    }

fn query_min(&self, index: usize) -> Option<L::Output>

Examples found in repository

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

    pub fn execute(self) -> Vec<Option<L::Output>> {
        let mut markers = Vec::with_capacity(2 * self.events.len());
        for (i, event) in self.events.iter().enumerate() {
            let i = i as u32;
            match *event {
                LiChaoEvent::Line(_) => {}
                LiChaoEvent::Segment(left, right, _) => {
                    markers.push((left, i << 2));
                    markers.push((right, i << 2 | 1));
                }
                LiChaoEvent::Query(x, _) => markers.push((x, i << 2 | 2)),
            }
        }
        markers.radix_sort_by_key(|&(x, _)| x);

        let mut positions = vec![[0u32; 2]; self.events.len()];
        let mut coordinates = Vec::with_capacity(self.queries);
        let mut left = 0;
        while left < markers.len() {
            let x = markers[left].0;
            let mut right = left + 1;
            while right < markers.len() && markers[right].0 == x {
                right += 1;
            }
            let index = coordinates.len() as u32;
            let mut queried = false;
            for &(_, marker) in &markers[left..right] {
                let event = (marker >> 2) as usize;
                match marker & 3 {
                    0 => positions[event][0] = index,
                    1 => positions[event][1] = index,
                    _ => {
                        positions[event][0] = index;
                        queried = true;
                    }
                }
            }
            if queried {
                coordinates.push(x);
            }
            left = right;
        }
        if let Some(&x) = coordinates.last() {
            coordinates.resize(coordinates.len().next_power_of_two(), x);
            coordinates.push(x);
        }

        let mut tree = IndexedLiChaoTree::new(&coordinates);
        let mut result = vec![None; self.queries];
        for (i, event) in self.events.into_iter().enumerate() {
            match event {
                LiChaoEvent::Line(line) => tree.add_line(line),
                LiChaoEvent::Segment(_, _, line) => {
                    let [left, right] = positions[i];
                    tree.add_segment(left as usize..right as usize, line);
                }
                LiChaoEvent::Query(_, output) => {
                    result[output as usize] = tree.query_min(positions[i][0] as usize);
                }
            }
        }
        result
    }