Struct ContourQueryRange 

pub struct ContourQueryRange {
    comp_range: Vec<usize>,
    info_indptr: Vec<usize>,
    infos: Vec<ContourInfo>,
    local_info: Vec<(usize, usize)>,
    local_offsets: Vec<usize>,
    local_masks: Vec<u32>,
}

Fields

comp_range: Vec<usize>

info_indptr: Vec<usize>

infos: Vec<ContourInfo>

local_info: Vec<(usize, usize)>

local_offsets: Vec<usize>

local_masks: Vec<u32>

Implementations

impl ContourQueryRange

pub fn len(&self) -> usize

Examples found in repository

crates/competitive/src/tree/centroid_decomposition.rs (line 186)

    pub fn is_empty(&self) -> bool {
        self.len() == 0
    }

pub fn is_empty(&self) -> bool

pub fn component_sizes(&self) -> impl ExactSizeIterator<Item = usize> + '_

Examples found in repository

crates/library_checker/src/tree/vertex_get_range_contour_add_on_tree.rs (line 19)

pub fn vertex_get_range_contour_add_on_tree(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n, q, mut a: [i64; n], (graph, _): @TreeGraphScanner::<usize, ()>::new(n));
    let cq = graph.contour_query_range();
    let mut bits: Vec<BinaryIndexedTree<AdditiveOperation<_>>> = cq
        .component_sizes()
        .map(|n| BinaryIndexedTree::new(n + 1))
        .collect();

    for _ in 0..q {
        sc!(query: Query);
        match query {
            Query::Add { v, l, r, x } => {
                cq.for_each_contour_range(v, l, r, |c, start, end| {
                    bits[c].update(start, x);
                    bits[c].update(end, -x);
                });
                if l == 0 && 0 < r {
                    a[v] += x;
                }
            }
            Query::Get { v } => {
                let mut ans = a[v];
                cq.for_each_index(v, |c, i| ans += bits[c].accumulate(i));
                pp!(ans);
            }
        }
    }
}

crates/library_checker/src/tree/vertex_add_range_contour_sum_on_tree.rs (line 18)

pub fn vertex_add_range_contour_sum_on_tree(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n, q, mut a: [i64; n], (graph, _): @TreeGraphScanner::<usize, ()>::new(n));
    let cq = graph.contour_query_range();
    let mut raw: Vec<_> = cq.component_sizes().map(|n| vec![0; n]).collect();
    for (v, &x) in a.iter().enumerate() {
        cq.for_each_index(v, |c, i| raw[c][i] += x);
    }
    let mut bits: Vec<BinaryIndexedTree<AdditiveOperation<_>>> = raw
        .into_iter()
        .map(|values| BinaryIndexedTree::from_slice(&values))
        .collect();
    for _ in 0..q {
        sc!(query: Query);
        match query {
            Query::Add { p, x } => {
                a[p] += x;
                cq.for_each_index(p, |c, i| bits[c].update(i, x));
            }
            Query::Sum { v, l, r } => {
                let mut ans = if l == 0 && 0 < r { a[v] } else { 0 };
                cq.for_each_contour_range(v, l, r, |c, start, end| {
                    ans += bits[c].fold_abelian(start, end);
                });
                pp!(ans);
            }
        }
    }
}

pub fn for_each_index(&self, v: usize, f: impl FnMut(usize, usize))

Calls f(component, index) for each position representing v.

Examples found in repository

crates/library_checker/src/tree/vertex_get_range_contour_add_on_tree.rs (line 37)

pub fn vertex_get_range_contour_add_on_tree(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n, q, mut a: [i64; n], (graph, _): @TreeGraphScanner::<usize, ()>::new(n));
    let cq = graph.contour_query_range();
    let mut bits: Vec<BinaryIndexedTree<AdditiveOperation<_>>> = cq
        .component_sizes()
        .map(|n| BinaryIndexedTree::new(n + 1))
        .collect();

    for _ in 0..q {
        sc!(query: Query);
        match query {
            Query::Add { v, l, r, x } => {
                cq.for_each_contour_range(v, l, r, |c, start, end| {
                    bits[c].update(start, x);
                    bits[c].update(end, -x);
                });
                if l == 0 && 0 < r {
                    a[v] += x;
                }
            }
            Query::Get { v } => {
                let mut ans = a[v];
                cq.for_each_index(v, |c, i| ans += bits[c].accumulate(i));
                pp!(ans);
            }
        }
    }
}

crates/library_checker/src/tree/vertex_add_range_contour_sum_on_tree.rs (line 20)

pub fn vertex_add_range_contour_sum_on_tree(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n, q, mut a: [i64; n], (graph, _): @TreeGraphScanner::<usize, ()>::new(n));
    let cq = graph.contour_query_range();
    let mut raw: Vec<_> = cq.component_sizes().map(|n| vec![0; n]).collect();
    for (v, &x) in a.iter().enumerate() {
        cq.for_each_index(v, |c, i| raw[c][i] += x);
    }
    let mut bits: Vec<BinaryIndexedTree<AdditiveOperation<_>>> = raw
        .into_iter()
        .map(|values| BinaryIndexedTree::from_slice(&values))
        .collect();
    for _ in 0..q {
        sc!(query: Query);
        match query {
            Query::Add { p, x } => {
                a[p] += x;
                cq.for_each_index(p, |c, i| bits[c].update(i, x));
            }
            Query::Sum { v, l, r } => {
                let mut ans = if l == 0 && 0 < r { a[v] } else { 0 };
                cq.for_each_contour_range(v, l, r, |c, start, end| {
                    ans += bits[c].fold_abelian(start, end);
                });
                pp!(ans);
            }
        }
    }
}

pub fn for_each_contour_range( &self, v: usize, l: usize, r: usize, f: impl FnMut(usize, usize, usize), )

Calls f(component, start, end) for disjoint ranges at distances in l..r from v. The ranges exclude v itself, even when l == 0.

Examples found in repository

crates/library_checker/src/tree/vertex_get_range_contour_add_on_tree.rs (lines 27-30)

pub fn vertex_get_range_contour_add_on_tree(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n, q, mut a: [i64; n], (graph, _): @TreeGraphScanner::<usize, ()>::new(n));
    let cq = graph.contour_query_range();
    let mut bits: Vec<BinaryIndexedTree<AdditiveOperation<_>>> = cq
        .component_sizes()
        .map(|n| BinaryIndexedTree::new(n + 1))
        .collect();

    for _ in 0..q {
        sc!(query: Query);
        match query {
            Query::Add { v, l, r, x } => {
                cq.for_each_contour_range(v, l, r, |c, start, end| {
                    bits[c].update(start, x);
                    bits[c].update(end, -x);
                });
                if l == 0 && 0 < r {
                    a[v] += x;
                }
            }
            Query::Get { v } => {
                let mut ans = a[v];
                cq.for_each_index(v, |c, i| ans += bits[c].accumulate(i));
                pp!(ans);
            }
        }
    }
}

crates/library_checker/src/tree/vertex_add_range_contour_sum_on_tree.rs (lines 35-37)

pub fn vertex_add_range_contour_sum_on_tree(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n, q, mut a: [i64; n], (graph, _): @TreeGraphScanner::<usize, ()>::new(n));
    let cq = graph.contour_query_range();
    let mut raw: Vec<_> = cq.component_sizes().map(|n| vec![0; n]).collect();
    for (v, &x) in a.iter().enumerate() {
        cq.for_each_index(v, |c, i| raw[c][i] += x);
    }
    let mut bits: Vec<BinaryIndexedTree<AdditiveOperation<_>>> = raw
        .into_iter()
        .map(|values| BinaryIndexedTree::from_slice(&values))
        .collect();
    for _ in 0..q {
        sc!(query: Query);
        match query {
            Query::Add { p, x } => {
                a[p] += x;
                cq.for_each_index(p, |c, i| bits[c].update(i, x));
            }
            Query::Sum { v, l, r } => {
                let mut ans = if l == 0 && 0 < r { a[v] } else { 0 };
                cq.for_each_contour_range(v, l, r, |c, start, end| {
                    ans += bits[c].fold_abelian(start, end);
                });
                pp!(ans);
            }
        }
    }
}

Trait Implementations

impl Clone for ContourQueryRange

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 ContourQueryRange

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

Formats the value using the given formatter.