fn next() -> i64 { static mut seed: i64 = 0xdeadc0de; unsafe { seed = seed.wrapping_mul(0x12345678deadc0d1).wrapping_add(0x1551); seed } } fn main() { const N: usize = 30000; let mut cur_depth = 0; let mut bst = None; for i in 0 .. N { let elem = (next() & 0xffff_ffff) as usize; bst = Node::insert(bst, elem); let dep = Node::depth(&bst); if cur_depth != dep { println!("i = {}, depth = {}", i, dep); cur_depth = dep; } } } #[allow(dead_code)] struct Node<T> { val: T, size: usize, left: Option<Box<Node<T>>>, right: Option<Box<Node<T>>>, depth: usize, priority: i64, } #[allow(dead_code)] type Link<T> = Option<Box<Node<T>>>; #[allow(dead_code)] impl<T: std::cmp::PartialOrd + Copy> Node<T> { fn singleton(val: T) -> Node<T> { Node { val: val, size: 1, left: None, right: None, depth: 1, priority: next() } } fn update(&mut self) { self.size = Self::size(&self.left) + Self::size(&self.right) + 1; self.depth = std::cmp::max(Self::depth(&self.left), Self::depth(&self.right)) + 1; } fn insert(n: Link<T>, new_val: T) -> Link<T> { let (left, right) = Self::split_less(n, new_val); let single = Some(Box::new(Node::singleton(new_val))); let n = Self::merge(left, single); Self::merge(n, right) } fn insert_at(n: Link<T>, k: usize, new_val: T) -> Link<T> { let (left, right) = Self::split_at(n, k); let single = Some(Box::new(Node::singleton(new_val))); let n = Self::merge(left, single); Self::merge(n, right) } fn merge(left: Link<T>, right: Link<T>) -> Link<T> { match (left, right) { (None, r) => r, (l, None) => l, (mut l, mut r) => { let mut l = l.take().unwrap(); let mut r = r.take().unwrap(); if r.priority < l.priority { let lr = (*l).right.take(); l.right = Self::merge(lr, Some(r)); l.update(); Some(l) } else { let rl = (*r).left.take(); r.left = Self::merge(Some(l), rl); r.update(); Some(r) } } } } fn split_less(n: Link<T>, val: T) -> (Link<T>, Link<T>) { Self::split_cmp_impl(n, &|n: &Box<Node<T>>| n.val < val) } fn split_leq(n: Link<T>, val: T) -> (Link<T>, Link<T>) { Self::split_cmp_impl(n, &|n: &Box<Node<T>>| n.val <= val) } fn split_cmp_impl(n: Link<T>, f: &Fn(&Box<Node<T>>) -> bool) -> (Link<T>, Link<T>) { match n { None => (None, None), Some(mut n) => { if f(&n) { let (l, r) = Self::split_cmp_impl(n.right.take(), f); n.right = l; n.update(); (Some(n), r) } else { let (l, r) = Self::split_cmp_impl(n.left.take(), f); n.left = r; n.update(); (l, Some(n)) } } } } fn split_at(n: Link<T>, k: usize) -> (Link<T>, Link<T>) { match n { None => (None, None), Some(mut n) => { let ls = Self::size(&n.left); if k <= ls { let nl = n.left.take(); let (l, r) = Self::split_at(nl, k); n.left = r; n.update(); (l, Some(n)) } else { let nr = n.right.take(); let (l, r) = Self::split_at(nr, k - ls - 1); n.right = l; n.update(); (Some(n), r) } } } } fn size(n: &Link<T>) -> usize { match n { &None => 0, &Some(ref n) => n.size, } } fn depth(n: &Link<T>) -> usize { match n { &None => 0, &Some(ref n) => n.depth, } } fn at(n: &Link<T>, k: usize) -> Option<T> { match n { &None => None, &Some(ref n) => { let ls = Node::size(&n.left); if k < ls { Self::at(&n.left, k) } else if k == ls { Some(n.val) } else { Self::at(&n.right, k - ls - 1) } } } } }
Standard input is empty
i = 0, depth = 1 i = 1, depth = 2 i = 2, depth = 3 i = 6, depth = 4 i = 7, depth = 5 i = 10, depth = 6 i = 13, depth = 7 i = 18, depth = 8 i = 29, depth = 9 i = 30, depth = 10 i = 45, depth = 11 i = 48, depth = 12 i = 49, depth = 13 i = 71, depth = 14 i = 87, depth = 15 i = 104, depth = 16 i = 134, depth = 17 i = 194, depth = 18 i = 202, depth = 19 i = 221, depth = 20 i = 279, depth = 18 i = 308, depth = 17 i = 313, depth = 18 i = 324, depth = 16 i = 339, depth = 17 i = 397, depth = 18 i = 409, depth = 16 i = 434, depth = 17 i = 437, depth = 18 i = 468, depth = 19 i = 606, depth = 20 i = 697, depth = 19 i = 710, depth = 20 i = 775, depth = 21 i = 842, depth = 19 i = 862, depth = 18 i = 875, depth = 19 i = 891, depth = 20 i = 901, depth = 21 i = 909, depth = 22 i = 1047, depth = 23 i = 1109, depth = 22 i = 1131, depth = 23 i = 1204, depth = 24 i = 1305, depth = 25 i = 1326, depth = 26 i = 1415, depth = 27 i = 1478, depth = 22 i = 1583, depth = 23 i = 1589, depth = 24 i = 1870, depth = 25 i = 1880, depth = 24 i = 1969, depth = 25 i = 2175, depth = 26 i = 2315, depth = 27 i = 2449, depth = 28 i = 2514, depth = 29 i = 2628, depth = 26 i = 2688, depth = 25 i = 2856, depth = 26 i = 2960, depth = 27 i = 3004, depth = 28 i = 3113, depth = 29 i = 3397, depth = 30 i = 3814, depth = 29 i = 3888, depth = 30 i = 3953, depth = 29 i = 3999, depth = 30 i = 4059, depth = 29 i = 4495, depth = 28 i = 4671, depth = 29 i = 4672, depth = 27 i = 4746, depth = 28 i = 4789, depth = 27 i = 4867, depth = 28 i = 4957, depth = 27 i = 5079, depth = 28 i = 5132, depth = 29 i = 6924, depth = 30 i = 8937, depth = 29 i = 9101, depth = 30 i = 9270, depth = 31 i = 9334, depth = 32 i = 10283, depth = 31 i = 10284, depth = 32 i = 11260, depth = 30 i = 11859, depth = 31 i = 12552, depth = 30 i = 12700, depth = 31 i = 12994, depth = 32 i = 13171, depth = 33 i = 13532, depth = 32 i = 13942, depth = 33 i = 14468, depth = 34 i = 14472, depth = 32 i = 15598, depth = 33 i = 16853, depth = 32 i = 17118, depth = 33 i = 17772, depth = 34 i = 17952, depth = 35 i = 19072, depth = 33 i = 19342, depth = 34 i = 19599, depth = 33 i = 21159, depth = 34 i = 21380, depth = 33 i = 22461, depth = 34 i = 23091, depth = 35 i = 24097, depth = 36 i = 24221, depth = 37 i = 25058, depth = 38 i = 25485, depth = 36 i = 25619, depth = 35 i = 27172, depth = 36 i = 27350, depth = 34 i = 28682, depth = 33 i = 29115, depth = 32 i = 29412, depth = 33 i = 29511, depth = 34