Struct Static2DTree

Source

pub struct Static2DTree<T, U, V>where
    T: Ord,
    U: Ord,{
    data: Vec<(T, U, V)>,
}

Fields§

§data: Vec<(T, U, V)>

Implementations§

Source §

impl<T, U, V> Static2DTree<T, U, V>
where T: Ord, U: Ord,

Source

pub fn new(data: I) -> Self
where I: IntoIterator<Item = (T, U, V)>,

Examples found in repository ?

crates/aizu_online_judge/src/dsl/dsl_2_c.rs (line 8)

5pub fn dsl_2_c(reader: impl Read, writer: impl Write) {
6    prepare_io!(reader, writer);
7    sc!(n, xy: [(i64, i64); iter n]);
8    let tree = Static2DTree::new(xy.enumerate().map(|(i, (x, y))| (x, y, i)));
9    sc!(q, query: [(i64, i64, i64, i64); iter q]);
10    for (sx, tx, sy, ty) in query {
11        let mut v = tree.range(sx..tx + 1, sy..ty + 1);
12        v.sort();
13        for v in v {
14            pp!(v);
15        }
16        pp!();
17    }
18}

Source

fn build(data: &mut [(T, U, V)], l: usize, r: usize, depth: usize)

Examples found in repository ?

crates/competitive/src/data_structure/kdtree.rs (line 21)

15    pub fn new<I>(data: I) -> Self
16    where
17        I: IntoIterator<Item = (T, U, V)>,
18    {
19        let mut data: Vec<_> = data.into_iter().collect();
20        let n = data.len();
21        Self::build(&mut data, 0, n, 0);
22        Self { data }
23    }
24    fn build(data: &mut [(T, U, V)], l: usize, r: usize, depth: usize) {
25        if r - l <= 1 {
26            return;
27        }
28        let m = l.midpoint(r);
29        if depth.is_multiple_of(2) {
30            data[l..r].select_nth_unstable_by(m - l, |p, q| p.0.cmp(&q.0));
31        } else {
32            data[l..r].select_nth_unstable_by(m - l, |p, q| p.1.cmp(&q.1));
33        }
34        Self::build(data, l, m, depth + 1);
35        Self::build(data, m + 1, r, depth + 1);
36    }

Source

pub fn range(&self, range1: Range<T>, range2: Range) -> Vec<&V>

Returns the values in the half-open rectangle. Their order is unspecified.

Examples found in repository ?

crates/aizu_online_judge/src/dsl/dsl_2_c.rs (line 11)

5pub fn dsl_2_c(reader: impl Read, writer: impl Write) {
6    prepare_io!(reader, writer);
7    sc!(n, xy: [(i64, i64); iter n]);
8    let tree = Static2DTree::new(xy.enumerate().map(|(i, (x, y))| (x, y, i)));
9    sc!(q, query: [(i64, i64, i64, i64); iter q]);
10    for (sx, tx, sy, ty) in query {
11        let mut v = tree.range(sx..tx + 1, sy..ty + 1);
12        v.sort();
13        for v in v {
14            pp!(v);
15        }
16        pp!();
17    }
18}

Source

fn range_inner<'a>( &'a self, range1: &Range<T>, range2: &Range, l: usize, r: usize, depth: usize, res: &mut Vec<&'a V>, )

Examples found in repository ?

crates/competitive/src/data_structure/kdtree.rs (line 40)

38    pub fn range(&self, range1: Range<T>, range2: Range<U>) -> Vec<&V> {
39        let mut res = vec![];
40        self.range_inner(&range1, &range2, 0, self.data.len(), 0, &mut res);
41        res
42    }
43    fn range_inner<'a>(
44        &'a self,
45        range1: &Range<T>,
46        range2: &Range<U>,
47        l: usize,
48        r: usize,
49        depth: usize,
50        res: &mut Vec<&'a V>,
51    ) {
52        if l < r {
53            let m = l.midpoint(r);
54            let (t, u, v) = &self.data[m];
55            if range1.contains(t) && range2.contains(u) {
56                res.push(v);
57            }
58            if if depth.is_multiple_of(2) {
59                &range1.start <= t
60            } else {
61                &range2.start <= u
62            } {
63                self.range_inner(range1, range2, l, m, depth + 1, res);
64            }
65            if if depth.is_multiple_of(2) {
66                t < &range1.end
67            } else {
68                u < &range2.end
69            } {
70                self.range_inner(range1, range2, m + 1, r, depth + 1, res);
71            }
72        }
73    }