competitive::tree::centroid_decomposition

Struct ContourQueryRange

pub struct ContourQueryRange {
    comp_range: Vec<usize>,
    info_indptr: Vec<usize>,
    infos: Vec<ContourInfo>,
}

Fields§

§comp_range: Vec<usize>§info_indptr: Vec<usize>§infos: Vec<ContourInfo>

Implementations§

Source §

impl ContourQueryRange

Source

pub fn len(&self) -> usize

Examples found in repository ?

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

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

More examples

Hide additional examples

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

16pub fn vertex_get_range_contour_add_on_tree(reader: impl Read, mut writer: impl Write) {
17    let s = read_all_unchecked(reader);
18    let mut scanner = Scanner::new(&s);
19    scan!(scanner, n, q, mut a: [i64; n], (graph, _): @TreeGraphScanner::<usize, ()>::new(n));
20    let cq = graph.contour_query_range();
21    let mut bit = BinaryIndexedTree::<AdditiveOperation<_>>::new(cq.len() + 1);
22
23    for _ in 0..q {
24        scan!(scanner, query: Query);
25        match query {
26            Query::Add { v, l, r, x } => {
27                cq.for_each_contour_range(v, l, r, |start, end| {
28                    bit.update(start, x);
29                    bit.update(end, -x);
30                });
31                if l == 0 && 0 < r {
32                    a[v] += x;
33                }
34            }
35            Query::Get { v } => {
36                let mut ans = a[v];
37                cq.for_each_index(v, |i| ans += bit.accumulate(i));
38                writeln!(writer, "{ans}").ok();
39            }
40        }
41    }
42}

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

16pub fn vertex_add_range_contour_sum_on_tree(reader: impl Read, mut writer: impl Write) {
17    let s = read_all_unchecked(reader);
18    let mut scanner = Scanner::new(&s);
19    scan!(scanner, n, q, mut a: [i64; n], (graph, _): @TreeGraphScanner::<usize, ()>::new(n));
20    let cq = graph.contour_query_range();
21    let mut raw = vec![0; cq.len()];
22    for (v, &x) in a.iter().enumerate() {
23        cq.for_each_index(v, |i| raw[i] += x);
24    }
25    let mut bit = BinaryIndexedTree::<AdditiveOperation<_>>::from_slice(&raw);
26    for _ in 0..q {
27        scan!(scanner, query: Query);
28        match query {
29            Query::Add { p, x } => {
30                a[p] += x;
31                cq.for_each_index(p, |i| bit.update(i, x));
32            }
33            Query::Sum { v, l, r } => {
34                let mut ans = if l == 0 && 0 < r { a[v] } else { 0 };
35                cq.for_each_contour_range(v, l, r, |start, end| {
36                    ans += bit.fold(start, end);
37                });
38                writeln!(writer, "{ans}").ok();
39            }
40        }
41    }
42}

Source

pub fn is_empty(&self) -> bool

Source

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

Examples found in repository ?

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

16pub fn vertex_get_range_contour_add_on_tree(reader: impl Read, mut writer: impl Write) {
17    let s = read_all_unchecked(reader);
18    let mut scanner = Scanner::new(&s);
19    scan!(scanner, n, q, mut a: [i64; n], (graph, _): @TreeGraphScanner::<usize, ()>::new(n));
20    let cq = graph.contour_query_range();
21    let mut bit = BinaryIndexedTree::<AdditiveOperation<_>>::new(cq.len() + 1);
22
23    for _ in 0..q {
24        scan!(scanner, query: Query);
25        match query {
26            Query::Add { v, l, r, x } => {
27                cq.for_each_contour_range(v, l, r, |start, end| {
28                    bit.update(start, x);
29                    bit.update(end, -x);
30                });
31                if l == 0 && 0 < r {
32                    a[v] += x;
33                }
34            }
35            Query::Get { v } => {
36                let mut ans = a[v];
37                cq.for_each_index(v, |i| ans += bit.accumulate(i));
38                writeln!(writer, "{ans}").ok();
39            }
40        }
41    }
42}

More examples

Hide additional examples

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

16pub fn vertex_add_range_contour_sum_on_tree(reader: impl Read, mut writer: impl Write) {
17    let s = read_all_unchecked(reader);
18    let mut scanner = Scanner::new(&s);
19    scan!(scanner, n, q, mut a: [i64; n], (graph, _): @TreeGraphScanner::<usize, ()>::new(n));
20    let cq = graph.contour_query_range();
21    let mut raw = vec![0; cq.len()];
22    for (v, &x) in a.iter().enumerate() {
23        cq.for_each_index(v, |i| raw[i] += x);
24    }
25    let mut bit = BinaryIndexedTree::<AdditiveOperation<_>>::from_slice(&raw);
26    for _ in 0..q {
27        scan!(scanner, query: Query);
28        match query {
29            Query::Add { p, x } => {
30                a[p] += x;
31                cq.for_each_index(p, |i| bit.update(i, x));
32            }
33            Query::Sum { v, l, r } => {
34                let mut ans = if l == 0 && 0 < r { a[v] } else { 0 };
35                cq.for_each_contour_range(v, l, r, |start, end| {
36                    ans += bit.fold(start, end);
37                });
38                writeln!(writer, "{ans}").ok();
39            }
40        }
41    }
42}

Source

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

Examples found in repository ?

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

16pub fn vertex_get_range_contour_add_on_tree(reader: impl Read, mut writer: impl Write) {
17    let s = read_all_unchecked(reader);
18    let mut scanner = Scanner::new(&s);
19    scan!(scanner, n, q, mut a: [i64; n], (graph, _): @TreeGraphScanner::<usize, ()>::new(n));
20    let cq = graph.contour_query_range();
21    let mut bit = BinaryIndexedTree::<AdditiveOperation<_>>::new(cq.len() + 1);
22
23    for _ in 0..q {
24        scan!(scanner, query: Query);
25        match query {
26            Query::Add { v, l, r, x } => {
27                cq.for_each_contour_range(v, l, r, |start, end| {
28                    bit.update(start, x);
29                    bit.update(end, -x);
30                });
31                if l == 0 && 0 < r {
32                    a[v] += x;
33                }
34            }
35            Query::Get { v } => {
36                let mut ans = a[v];
37                cq.for_each_index(v, |i| ans += bit.accumulate(i));
38                writeln!(writer, "{ans}").ok();
39            }
40        }
41    }
42}

More examples

Hide additional examples

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

16pub fn vertex_add_range_contour_sum_on_tree(reader: impl Read, mut writer: impl Write) {
17    let s = read_all_unchecked(reader);
18    let mut scanner = Scanner::new(&s);
19    scan!(scanner, n, q, mut a: [i64; n], (graph, _): @TreeGraphScanner::<usize, ()>::new(n));
20    let cq = graph.contour_query_range();
21    let mut raw = vec![0; cq.len()];
22    for (v, &x) in a.iter().enumerate() {
23        cq.for_each_index(v, |i| raw[i] += x);
24    }
25    let mut bit = BinaryIndexedTree::<AdditiveOperation<_>>::from_slice(&raw);
26    for _ in 0..q {
27        scan!(scanner, query: Query);
28        match query {
29            Query::Add { p, x } => {
30                a[p] += x;
31                cq.for_each_index(p, |i| bit.update(i, x));
32            }
33            Query::Sum { v, l, r } => {
34                let mut ans = if l == 0 && 0 < r { a[v] } else { 0 };
35                cq.for_each_contour_range(v, l, r, |start, end| {
36                    ans += bit.fold(start, end);
37                });
38                writeln!(writer, "{ans}").ok();
39            }
40        }
41    }
42}