Struct CartesianTree 

pub struct CartesianTree {
    pub root: usize,
    pub parents: Vec<usize>,
    pub children: Vec<[usize; 2]>,
}

Fields

root: usize

parents: Vec<usize>

children: Vec<[usize; 2]>

Implementations

impl CartesianTree

pub fn new<T>(a: &[T]) -> Self

where T: PartialOrd,

Examples found in repository

crates/library_checker/src/tree/cartesian_tree.rs (line 8)

pub fn cartesian_tree(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n, a: [i32; n]);
    let ct = CartesianTree::new(&a);
    pp!(@it ct.parents.iter().map(|&p| if p == !0 { ct.root } else { p }));
}

crates/competitive/src/tree/heavy_light_decomposition.rs (line 394)

    pub fn build_fold<M: Monoid>(&self, values: &[M::T]) -> HeavyLightPathFold<'_, M> {
        assert_eq!(values.len(), self.len());
        let mut fold = HeavyLightPathFold {
            tree: self,
            nodes: self
                .order
                .iter()
                .map(|&v| PathFoldNode {
                    parent: u32::MAX,
                    children: [u32::MAX; 2],
                    priority: 0,
                    value: values[v].clone(),
                    aggregate: [values[v].clone(), values[v].clone()],
                    prefix: [values[v].clone(), values[v].clone()],
                })
                .collect(),
        };
        let mut start = 0;
        let mut priorities = Vec::new();
        let mut stack = Vec::new();
        while start < self.len() {
            let mut end = start + 1;
            while end < self.len() && self.nodes[self.order[end]].head as usize == start {
                end += 1;
            }
            priorities.clear();
            let mut sum = 0usize;
            for i in start..end {
                let weight = self.subtree_size(self.order[i])
                    - if i + 1 < end {
                        self.subtree_size(self.order[i + 1])
                    } else {
                        0
                    };
                let priority = (sum ^ (sum + weight)).ilog2();
                sum += weight;
                fold.nodes[i].priority = priority;
                priorities.push(std::cmp::Reverse(priority));
            }
            let cartesian = CartesianTree::new(&priorities);
            for i in start..end {
                let parent = cartesian.parents[i - start];
                fold.nodes[i].parent = if parent == usize::MAX {
                    u32::MAX
                } else {
                    (parent + start) as u32
                };
                fold.nodes[i].children = cartesian.children[i - start].map(|v| {
                    if v == usize::MAX {
                        u32::MAX
                    } else {
                        (v + start) as u32
                    }
                });
            }
            stack.clear();
            stack.push(cartesian.root + start);
            let mut i = 0;
            while i < stack.len() {
                stack.extend(
                    fold.nodes[stack[i]]
                        .children
                        .into_iter()
                        .filter(|&v| v != u32::MAX)
                        .map(|v| v as usize),
                );
                i += 1;
            }
            for &i in stack.iter().rev() {
                fold.pull(i);
            }
            start = end;
        }
        fold
    }

pub fn with_ranges(&self, f: impl FnMut(usize, Range<usize>))

Trait Implementations

impl Clone for CartesianTree

fn clone(&self) -> Self

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for CartesianTree

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

Formats the value using the given formatter.