Struct RangeMinimumQuery 

pub struct RangeMinimumQuery<T> {
    data: Vec<T>,
    suffix: Vec<T>,
    prefix: Vec<T>,
    table: Vec<T>,
    blocks: usize,
}

Fields

data: Vec<T>

suffix: Vec<T>

prefix: Vec<T>

table: Vec<T>

blocks: usize

Implementations

impl<T> RangeMinimumQuery<T>

where T: Ord + Copy,

pub fn new(data: Vec<T>) -> Self

Examples found in repository

crates/library_checker/src/data_structure/staticrmq.rs (line 31)

pub fn staticrmq_range_minimum_query(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n, q, a: [u64; n], lr: [(usize, usize); iter q]);
    let rmq = RangeMinimumQuery::new(a);
    for (l, r) in lr {
        pp!(rmq.fold(l, r));
    }
}

crates/competitive/src/string/string_search.rs (line 74)

    pub fn new(text: Vec<T>) -> Self {
        let suffix_array = SuffixArray::new(&text);

        let (lcp_array, rank) = suffix_array.lcp_array_with_rank(&text);
        let rmq = RangeMinimumQuery::new(lcp_array.clone());

        Self {
            text,
            suffix_array,
            lcp_array,
            rank,
            rmq,
        }
    }

crates/competitive/src/tree/euler_tour.rs (line 302)

    pub fn from_parents(parents: &[usize]) -> Self {
        let n = parents.len();
        let root = parents.iter().position(|&parent| parent == !0).unwrap();
        let mut depth = vec![!0u32; n];
        depth[root] = 0;
        let mut label_to_node = Vec::with_capacity(n);
        let mut node_to_label = vec![0u32; n];
        label_to_node.push(root as u32);
        let mut path = Vec::new();
        for mut u in 0..n {
            if depth[u] != !0 {
                continue;
            }
            if depth[parents[u]] != !0 {
                depth[u] = depth[parents[u]] + 1;
                node_to_label[u] = label_to_node.len() as u32;
                label_to_node.push(u as u32);
                continue;
            }
            while depth[u] == !0 {
                path.push(u);
                u = parents[u];
            }
            while let Some(u) = path.pop() {
                depth[u] = depth[parents[u]] + 1;
                node_to_label[u] = label_to_node.len() as u32;
                label_to_node.push(u as u32);
            }
        }

        let mut label_to_index = vec![0u32; n];
        for i in (1..n).rev() {
            let u = label_to_node[i] as usize;
            let parent = node_to_label[parents[u]] as usize;
            label_to_index[parent] += label_to_index[i] + 1;
        }
        for i in 1..n {
            let u = label_to_node[i] as usize;
            let parent = node_to_label[parents[u]] as usize;
            let descendants = label_to_index[i];
            let next = label_to_index[parent];
            label_to_index[i] = next;
            label_to_index[parent] = next - descendants - 1;
        }

        let mut index_to_parent = vec![0u32; n];
        for label in (1..n).rev() {
            let u = label_to_node[label] as usize;
            index_to_parent[label_to_index[label] as usize] = node_to_label[parents[u]];
            node_to_label[u] = label_to_index[label];
        }

        Self {
            node_to_index: node_to_label,
            label_to_node,
            rmq: RangeMinimumQuery::new(index_to_parent),
            depth,
        }
    }

    /// `order` must be a DFS preorder containing every vertex in `parents` exactly once.
    /// `parents` uses `!0` for the root.
    pub fn from_dfs_preorder(parents: &[usize], order: &[usize]) -> Self {
        let n = parents.len();
        let mut node_to_index = vec![0u32; n];
        for (i, &u) in order.iter().enumerate() {
            node_to_index[u] = i as u32;
        }
        let mut depth = vec![0u32; n];
        let mut index_to_parent = vec![0u32; n];
        for (i, &u) in order.iter().enumerate().skip(1) {
            let p = parents[u];
            depth[u] = depth[p] + 1;
            index_to_parent[i] = node_to_index[p];
        }
        Self {
            node_to_index,
            label_to_node: order.iter().map(|&u| u as u32).collect(),
            rmq: RangeMinimumQuery::new(index_to_parent),
            depth,
        }
    }

pub fn fold(&self, l: usize, r: usize) -> T

Examples found in repository

crates/competitive/src/string/string_search.rs (line 146)

    fn lcp_sa(&self, a: usize, b: usize) -> usize {
        if a == b {
            return self.text.len() - self.suffix_array[a];
        }
        let (l, r) = if a < b { (a, b) } else { (b, a) };
        self.rmq.fold(l, r)
    }

crates/library_checker/src/data_structure/staticrmq.rs (line 33)

pub fn staticrmq_range_minimum_query(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n, q, a: [u64; n], lr: [(usize, usize); iter q]);
    let rmq = RangeMinimumQuery::new(a);
    for (l, r) in lr {
        pp!(rmq.fold(l, r));
    }
}

crates/competitive/src/tree/euler_tour.rs (line 342)

    pub fn lca(&self, u: usize, v: usize) -> usize {
        if u == v {
            return u;
        }
        let u = self.node_to_index[u] as usize;
        let v = self.node_to_index[v] as usize;
        let label = self.rmq.fold(u.min(v) + 1, u.max(v) + 1) as usize;
        self.label_to_node[label] as usize
    }

Trait Implementations

impl<T: Clone> Clone for RangeMinimumQuery<T>

fn clone(&self) -> Self

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<T: Debug> Debug for RangeMinimumQuery<T>

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

Formats the value using the given formatter.