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 {
bst = Node::insert(bst, i);
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)
}
}
}
}
}
Zm4gbmV4dCgpIC0+IGk2NCB7CiAgICBzdGF0aWMgbXV0IHNlZWQ6IGk2NCA9IDB4ZGVhZGMwZGU7CiAgICB1bnNhZmUgewogICAgICAgIHNlZWQgPSBzZWVkLndyYXBwaW5nX211bCgweDEyMzQ1Njc4ZGVhZGMwZDEpLndyYXBwaW5nX2FkZCgweDE1NTEpOwogICAgICAgIHNlZWQKICAgIH0KfQoKZm4gbWFpbigpIHsKICAgIGNvbnN0IE46IHVzaXplID0gMzAwMDA7CiAgICBsZXQgbXV0IGN1cl9kZXB0aCA9IDA7CiAgICBsZXQgbXV0IGJzdCA9IE5vbmU7CiAgICBmb3IgaSBpbiAwIC4uIE4gewogICAgICAgIGJzdCA9IE5vZGU6Omluc2VydChic3QsIGkpOwogICAgICAgIGxldCBkZXAgPSBOb2RlOjpkZXB0aCgmYnN0KTsKICAgICAgICBpZiBjdXJfZGVwdGggIT0gZGVwIHsKICAgICAgICAgICAgcHJpbnRsbiEoImkgPSB7fSwgZGVwdGggPSB7fSIsIGksIGRlcCk7CiAgICAgICAgICAgIGN1cl9kZXB0aCA9IGRlcDsKICAgICAgICB9CiAgICB9Cn0KCgojW2FsbG93KGRlYWRfY29kZSldCnN0cnVjdCBOb2RlPFQ+IHsKICAgIHZhbDogVCwKICAgIHNpemU6IHVzaXplLAogICAgbGVmdDogT3B0aW9uPEJveDxOb2RlPFQ+Pj4sCiAgICByaWdodDogT3B0aW9uPEJveDxOb2RlPFQ+Pj4sCiAgICBkZXB0aDogdXNpemUsCiAgICBwcmlvcml0eTogaTY0LAp9CgojW2FsbG93KGRlYWRfY29kZSldCnR5cGUgTGluazxUPiA9IE9wdGlvbjxCb3g8Tm9kZTxUPj4+OwoKI1thbGxvdyhkZWFkX2NvZGUpXQppbXBsPFQ6IHN0ZDo6Y21wOjpQYXJ0aWFsT3JkICsgQ29weT4gTm9kZTxUPiB7CiAgICBmbiBzaW5nbGV0b24odmFsOiBUKSAtPiBOb2RlPFQ+IHsKICAgICAgICBOb2RlIHsKICAgICAgICAgICAgdmFsOiB2YWwsCiAgICAgICAgICAgIHNpemU6IDEsCiAgICAgICAgICAgIGxlZnQ6IE5vbmUsCiAgICAgICAgICAgIHJpZ2h0OiBOb25lLAogICAgICAgICAgICBkZXB0aDogMSwKICAgICAgICAgICAgcHJpb3JpdHk6IG5leHQoKQogICAgICAgIH0KICAgIH0KCiAgICBmbiB1cGRhdGUoJm11dCBzZWxmKSB7CiAgICAgICAgc2VsZi5zaXplID0gU2VsZjo6c2l6ZSgmc2VsZi5sZWZ0KSArIFNlbGY6OnNpemUoJnNlbGYucmlnaHQpICsgMTsKICAgICAgICBzZWxmLmRlcHRoID0gc3RkOjpjbXA6Om1heChTZWxmOjpkZXB0aCgmc2VsZi5sZWZ0KSwgU2VsZjo6ZGVwdGgoJnNlbGYucmlnaHQpKSArIDE7CiAgICB9CgogICAgZm4gaW5zZXJ0KG46IExpbms8VD4sIG5ld192YWw6IFQpIC0+IExpbms8VD4gewogICAgICAgIGxldCAobGVmdCwgcmlnaHQpID0gU2VsZjo6c3BsaXRfbGVzcyhuLCBuZXdfdmFsKTsKICAgICAgICBsZXQgc2luZ2xlID0gU29tZShCb3g6Om5ldyhOb2RlOjpzaW5nbGV0b24obmV3X3ZhbCkpKTsKICAgICAgICBsZXQgbiA9IFNlbGY6Om1lcmdlKGxlZnQsIHNpbmdsZSk7CiAgICAgICAgU2VsZjo6bWVyZ2UobiwgcmlnaHQpCiAgICB9CgogICAgZm4gaW5zZXJ0X2F0KG46IExpbms8VD4sIGs6IHVzaXplLCBuZXdfdmFsOiBUKSAtPiBMaW5rPFQ+IHsKICAgICAgICBsZXQgKGxlZnQsIHJpZ2h0KSA9IFNlbGY6OnNwbGl0X2F0KG4sIGspOwogICAgICAgIGxldCBzaW5nbGUgPSBTb21lKEJveDo6bmV3KE5vZGU6OnNpbmdsZXRvbihuZXdfdmFsKSkpOwogICAgICAgIGxldCBuID0gU2VsZjo6bWVyZ2UobGVmdCwgc2luZ2xlKTsKICAgICAgICBTZWxmOjptZXJnZShuLCByaWdodCkKICAgIH0KCiAgICBmbiBtZXJnZShsZWZ0OiBMaW5rPFQ+LCByaWdodDogTGluazxUPikgLT4gTGluazxUPiB7CiAgICAgICAgbWF0Y2ggKGxlZnQsIHJpZ2h0KSB7CiAgICAgICAgICAgIChOb25lLCByKSA9PiByLAogICAgICAgICAgICAobCwgTm9uZSkgPT4gbCwKICAgICAgICAgICAgKG11dCBsLCBtdXQgcikgPT4gewogICAgICAgICAgICAgICAgbGV0IG11dCBsID0gbC50YWtlKCkudW53cmFwKCk7CiAgICAgICAgICAgICAgICBsZXQgbXV0IHIgPSByLnRha2UoKS51bndyYXAoKTsKICAgICAgICAgICAgICAgIGlmIHIucHJpb3JpdHkgPCBsLnByaW9yaXR5IHsKICAgICAgICAgICAgICAgICAgICBsZXQgbHIgPSAoKmwpLnJpZ2h0LnRha2UoKTsKICAgICAgICAgICAgICAgICAgICBsLnJpZ2h0ID0gU2VsZjo6bWVyZ2UobHIsIFNvbWUocikpOwogICAgICAgICAgICAgICAgICAgIGwudXBkYXRlKCk7CiAgICAgICAgICAgICAgICAgICAgU29tZShsKQogICAgICAgICAgICAgICAgfSBlbHNlIHsKICAgICAgICAgICAgICAgICAgICBsZXQgcmwgPSAoKnIpLmxlZnQudGFrZSgpOwogICAgICAgICAgICAgICAgICAgIHIubGVmdCA9IFNlbGY6Om1lcmdlKFNvbWUobCksIHJsKTsKICAgICAgICAgICAgICAgICAgICByLnVwZGF0ZSgpOwogICAgICAgICAgICAgICAgICAgIFNvbWUocikKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgfQogICAgICAgIH0KICAgIH0KCiAgICBmbiBzcGxpdF9sZXNzKG46IExpbms8VD4sIHZhbDogVCkgLT4gKExpbms8VD4sIExpbms8VD4pIHsKICAgICAgICBTZWxmOjpzcGxpdF9jbXBfaW1wbChuLCAmfG46ICZCb3g8Tm9kZTxUPj58IG4udmFsIDwgdmFsKQogICAgfQoKICAgIGZuIHNwbGl0X2xlcShuOiBMaW5rPFQ+LCB2YWw6IFQpIC0+IChMaW5rPFQ+LCBMaW5rPFQ+KSB7CiAgICAgICAgU2VsZjo6c3BsaXRfY21wX2ltcGwobiwgJnxuOiAmQm94PE5vZGU8VD4+fCBuLnZhbCA8PSB2YWwpCiAgICB9CgogICAgZm4gc3BsaXRfY21wX2ltcGwobjogTGluazxUPiwgZjogJkZuKCZCb3g8Tm9kZTxUPj4pIC0+IGJvb2wpIC0+IChMaW5rPFQ+LCBMaW5rPFQ+KSB7CiAgICAgICAgbWF0Y2ggbiB7CiAgICAgICAgICAgIE5vbmUgPT4gKE5vbmUsIE5vbmUpLAogICAgICAgICAgICBTb21lKG11dCBuKSA9PiB7CiAgICAgICAgICAgICAgICBpZiBmKCZuKSB7CiAgICAgICAgICAgICAgICAgICAgbGV0IChsLCByKSA9IFNlbGY6OnNwbGl0X2NtcF9pbXBsKG4ucmlnaHQudGFrZSgpLCBmKTsKICAgICAgICAgICAgICAgICAgICBuLnJpZ2h0ID0gbDsKICAgICAgICAgICAgICAgICAgICBuLnVwZGF0ZSgpOwogICAgICAgICAgICAgICAgICAgIChTb21lKG4pLCByKQogICAgICAgICAgICAgICAgfSBlbHNlIHsKICAgICAgICAgICAgICAgICAgICBsZXQgKGwsIHIpID0gU2VsZjo6c3BsaXRfY21wX2ltcGwobi5sZWZ0LnRha2UoKSwgZik7CiAgICAgICAgICAgICAgICAgICAgbi5sZWZ0ID0gcjsKICAgICAgICAgICAgICAgICAgICBuLnVwZGF0ZSgpOwogICAgICAgICAgICAgICAgICAgIChsLCBTb21lKG4pKQogICAgICAgICAgICAgICAgfQogICAgICAgICAgICB9CiAgICAgICAgfQogICAgfQoKICAgIGZuIHNwbGl0X2F0KG46IExpbms8VD4sIGs6IHVzaXplKSAtPiAoTGluazxUPiwgTGluazxUPikgewogICAgICAgIG1hdGNoIG4gewogICAgICAgICAgICBOb25lID0+IChOb25lLCBOb25lKSwKICAgICAgICAgICAgU29tZShtdXQgbikgPT4gewogICAgICAgICAgICAgICAgbGV0IGxzID0gU2VsZjo6c2l6ZSgmbi5sZWZ0KTsKICAgICAgICAgICAgICAgIGlmIGsgPD0gbHMgewogICAgICAgICAgICAgICAgICAgIGxldCBubCA9IG4ubGVmdC50YWtlKCk7CiAgICAgICAgICAgICAgICAgICAgbGV0IChsLCByKSA9IFNlbGY6OnNwbGl0X2F0KG5sLCBrKTsKICAgICAgICAgICAgICAgICAgICBuLmxlZnQgPSByOwogICAgICAgICAgICAgICAgICAgIG4udXBkYXRlKCk7CiAgICAgICAgICAgICAgICAgICAgKGwsIFNvbWUobikpCiAgICAgICAgICAgICAgICB9IGVsc2UgewogICAgICAgICAgICAgICAgICAgIGxldCBuciA9IG4ucmlnaHQudGFrZSgpOwogICAgICAgICAgICAgICAgICAgIGxldCAobCwgcikgPSBTZWxmOjpzcGxpdF9hdChuciwgayAtIGxzIC0gMSk7CiAgICAgICAgICAgICAgICAgICAgbi5yaWdodCA9IGw7CiAgICAgICAgICAgICAgICAgICAgbi51cGRhdGUoKTsKICAgICAgICAgICAgICAgICAgICAoU29tZShuKSwgcikKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgfQogICAgICAgIH0KICAgIH0KCiAgICBmbiBzaXplKG46ICZMaW5rPFQ+KSAtPiB1c2l6ZSB7CiAgICAgICAgbWF0Y2ggbiB7CiAgICAgICAgICAgICZOb25lID0+IDAsCiAgICAgICAgICAgICZTb21lKHJlZiBuKSA9PiBuLnNpemUsCiAgICAgICAgfQogICAgfQoKICAgIGZuIGRlcHRoKG46ICZMaW5rPFQ+KSAtPiB1c2l6ZSB7CiAgICAgICAgbWF0Y2ggbiB7CiAgICAgICAgICAgICZOb25lID0+IDAsCiAgICAgICAgICAgICZTb21lKHJlZiBuKSA9PiBuLmRlcHRoLAogICAgICAgIH0KICAgIH0KCiAgICBmbiBhdChuOiAmTGluazxUPiwgazogdXNpemUpIC0+IE9wdGlvbjxUPiB7CiAgICAgICAgbWF0Y2ggbiB7CiAgICAgICAgICAgICZOb25lID0+IE5vbmUsCiAgICAgICAgICAgICZTb21lKHJlZiBuKSA9PiB7CiAgICAgICAgICAgICAgICBsZXQgbHMgPSBOb2RlOjpzaXplKCZuLmxlZnQpOwogICAgICAgICAgICAgICAgaWYgayA8IGxzIHsKICAgICAgICAgICAgICAgICAgICBTZWxmOjphdCgmbi5sZWZ0LCBrKQogICAgICAgICAgICAgICAgfSBlbHNlIGlmIGsgPT0gbHMgewogICAgICAgICAgICAgICAgICAgIFNvbWUobi52YWwpCiAgICAgICAgICAgICAgICB9IGVsc2UgewogICAgICAgICAgICAgICAgICAgIFNlbGY6OmF0KCZuLnJpZ2h0LCBrIC0gbHMgLSAxKQogICAgICAgICAgICAgICAgfQogICAgICAgICAgICB9CiAgICAgICAgfQogICAgfQp9Cgo=
i = 0, depth = 1
i = 1, depth = 2
i = 2, depth = 3
i = 3, depth = 4
i = 5, depth = 5
i = 6, depth = 6
i = 9, depth = 7
i = 18, depth = 8
i = 21, depth = 9
i = 30, depth = 10
i = 53, depth = 11
i = 56, depth = 12
i = 87, depth = 13
i = 91, depth = 14
i = 99, depth = 15
i = 138, depth = 16
i = 457, depth = 17
i = 531, depth = 18
i = 540, depth = 19
i = 562, depth = 20
i = 1295, depth = 21
i = 1395, depth = 22
i = 1421, depth = 23
i = 1429, depth = 24
i = 1882, depth = 25
i = 2352, depth = 26
i = 2834, depth = 27
i = 2957, depth = 28
i = 3167, depth = 29
i = 12634, depth = 30
i = 12786, depth = 31
i = 17875, depth = 32
i = 18541, depth = 33
i = 18669, depth = 34
i = 27158, depth = 35