結果

問題 No.649 ここでちょっとQK!
ユーザー kn_rew
提出日時 2025-03-16 23:47:08
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 250 ms / 3,000 ms
コード長 30,114 bytes
コンパイル時間 17,182 ms
コンパイル使用メモリ 401,976 KB
実行使用メモリ 15,616 KB
最終ジャッジ日時 2025-03-16 23:47:32
合計ジャッジ時間 20,517 ms
ジャッジサーバーID
(参考情報)
judge1 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 4
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff #

use proconio::{fastout, input};
use reprol::ds::avl_tree_multi_set::AvlTreeMultiSet;

#[fastout]
fn main() {
    input! {
        q: usize,
        k: usize,
    }

    let mut ms = AvlTreeMultiSet::new();

    for _ in 0..q {
        input! {
            t: i32,
        }
        if t == 1 {
            input! {
                v: u64,
            }
            ms.insert(v);
        } else {
            if ms.len() >= k {
                let ans = ms.remove_by_index(k - 1).unwrap();
                println!("{}", ans);
            } else {
                println!("-1");
                continue;
            }
        }
    }
}

#[allow(dead_code)]
pub mod reprol {
    pub mod ds {
        pub mod avl_tree_multi_set {
            use crate::reprol::ds::avl_tree_vec::{AvlTreeVec, IntoIter, Iter};
            use std::{
                cmp::Ordering,
                fmt::Debug,
                hash::Hash,
                mem::{swap, take},
                ops::Index,
            };
            pub struct AvlTreeMultiSet<T> {
                vec: AvlTreeVec<T>,
            }
            impl<T> AvlTreeMultiSet<T> {
                pub fn new() -> Self {
                    Self::default()
                }
                pub fn clear(&mut self) {
                    *self = Self::new();
                }
                pub fn len(&self) -> usize {
                    self.vec.len()
                }
                pub fn is_empty(&self) -> bool {
                    self.vec.is_empty()
                }
                pub fn insert(&mut self, value: T) -> bool
                where
                    T: Ord,
                {
                    let i = self.vec.lower_bound(&value);
                    self.vec.insert(i, value);
                    true
                }
                pub fn contains(&self, value: &T) -> bool
                where
                    T: Ord,
                {
                    let i = self.vec.lower_bound(value);
                    self.vec.get(i).is_some_and(|e| e == value)
                }
                pub fn count(&self, value: &T) -> usize
                where
                    T: Ord,
                {
                    self.vec.upper_bound(value) - self.vec.lower_bound(value)
                }
                pub fn remove(&mut self, value: &T) -> bool
                where
                    T: Ord,
                {
                    let i = self.vec.lower_bound(value);
                    if self.vec.get(i).is_some_and(|e| e == value) {
                        self.vec.remove(i);
                        true
                    } else {
                        false
                    }
                }
                pub fn remove_by_index(&mut self, index: usize) -> Option<T> {
                    self.vec.remove(index)
                }
                pub fn append(&mut self, other: &mut Self)
                where
                    T: Ord,
                {
                    if self.len() < other.len() {
                        swap(self, other);
                    }
                    take(&mut other.vec).into_iter().for_each(|item| {
                        self.insert(item);
                    });
                }
                pub fn split_off(&mut self, value: &T) -> Self
                where
                    T: Ord,
                {
                    let i = self.vec.lower_bound(value);
                    let sub = self.vec.split_off(i);
                    Self { vec: sub }
                }
                pub fn nth(&self, index: usize) -> Option<&T> {
                    self.vec.get(index)
                }
                pub fn nth_back(&self, index: usize) -> Option<&T> {
                    self.vec.get(self.vec.len().checked_sub(index + 1)?)
                }
                pub fn iter(&self) -> Iter<'_, T> {
                    self.vec.iter()
                }
            }
            impl<T> Default for AvlTreeMultiSet<T> {
                fn default() -> Self {
                    Self {
                        vec: AvlTreeVec::default(),
                    }
                }
            }
            impl<T> Index<usize> for AvlTreeMultiSet<T> {
                type Output = T;
                fn index(&self, index: usize) -> &Self::Output {
                    self.nth(index).unwrap()
                }
            }
            impl<'a, T> IntoIterator for &'a AvlTreeMultiSet<T> {
                type IntoIter = Iter<'a, T>;
                type Item = &'a T;
                fn into_iter(self) -> Self::IntoIter {
                    self.iter()
                }
            }
            impl<T> IntoIterator for AvlTreeMultiSet<T> {
                type IntoIter = IntoIter<T>;
                type Item = T;
                fn into_iter(self) -> Self::IntoIter {
                    self.vec.into_iter()
                }
            }
            impl<T: PartialEq> PartialEq for AvlTreeMultiSet<T> {
                fn eq(&self, other: &Self) -> bool {
                    self.iter().eq(other.iter())
                }
            }
            impl<T: Eq> Eq for AvlTreeMultiSet<T> {}
            impl<T: PartialOrd> PartialOrd for AvlTreeMultiSet<T> {
                fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
                    self.iter().partial_cmp(other.iter())
                }
            }
            impl<T: Ord> Ord for AvlTreeMultiSet<T> {
                fn cmp(&self, other: &Self) -> Ordering {
                    self.iter().cmp(other.iter())
                }
            }
            impl<T: Hash> Hash for AvlTreeMultiSet<T> {
                fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
                    self.iter().for_each(|item| item.hash(state));
                }
            }
            impl<T: Ord> Extend<T> for AvlTreeMultiSet<T> {
                fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
                    iter.into_iter().for_each(|x| {
                        self.insert(x);
                    });
                }
            }
            impl<'a, T: 'a + Ord + Copy> Extend<&'a T> for AvlTreeMultiSet<T> {
                fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
                    self.extend(iter.into_iter().cloned());
                }
            }
            impl<T: Ord> FromIterator<T> for AvlTreeMultiSet<T> {
                fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
                    let mut res = Self::new();
                    res.extend(iter);
                    res
                }
            }
            impl<T: Ord> From<Vec<T>> for AvlTreeMultiSet<T> {
                fn from(v: Vec<T>) -> Self {
                    Self::from_iter(v)
                }
            }
            impl<T: Ord, const N: usize> From<[T; N]> for AvlTreeMultiSet<T> {
                fn from(v: [T; N]) -> Self {
                    Self::from_iter(v)
                }
            }
            impl<T: Clone> Clone for AvlTreeMultiSet<T> {
                fn clone(&self) -> Self {
                    Self {
                        vec: self.vec.clone(),
                    }
                }
            }
            impl<T: Debug> Debug for AvlTreeMultiSet<T> {
                fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
                    f.debug_set().entries(self.iter()).finish()
                }
            }
        }
        pub mod avl_tree_vec {
            use std::{
                cmp::Ordering,
                fmt::Debug,
                hash::Hash,
                marker::PhantomData,
                ops::{Index, IndexMut},
                ptr::NonNull,
            };
            struct Node<T> {
                value: T,
                len: usize,
                height: i32,
                left: Link<T>,
                right: Link<T>,
            }
            type NodePtr<T> = NonNull<Node<T>>;
            type Link<T> = Option<NodePtr<T>>;
            impl<T> Node<T> {
                fn new(value: T) -> NodePtr<T> {
                    let node = Self {
                        value,
                        len: 1,
                        height: 1,
                        left: None,
                        right: None,
                    };
                    NonNull::from(Box::leak(Box::new(node)))
                }
                #[inline]
                fn fetch(&mut self) {
                    self.len = len(self.left) + len(self.right) + 1;
                    self.height = height(self.left).max(height(self.right)) + 1;
                }
            }
            #[inline]
            fn free<T>(node: NodePtr<T>) {
                unsafe { drop(Box::from_raw(node.as_ptr())) };
            }
            #[inline]
            fn len<T>(node: Link<T>) -> usize {
                node.map_or(0, |node| unsafe { node.as_ref() }.len)
            }
            #[inline]
            fn height<T>(node: Link<T>) -> i32 {
                node.map_or(0, |node| unsafe { node.as_ref() }.height)
            }
            #[inline]
            fn diff_height<T>(node: Link<T>) -> i32 {
                node.map_or(0, |node| {
                    let node = unsafe { node.as_ref() };
                    height(node.left) - height(node.right)
                })
            }
            fn balance<T>(mut root: Link<T>) -> Link<T> {
                fn rotate_right<T>(root: &mut Link<T>) {
                    *root = {
                        unsafe {
                            let mut root = root.unwrap();
                            let raw_root = root.as_mut();
                            let mut left = raw_root.left.unwrap();
                            let raw_left = left.as_mut();
                            raw_root.left = raw_left.right;
                            raw_root.fetch();
                            raw_left.right = Some(root);
                            raw_left.fetch();
                            Some(left)
                        }
                    };
                }
                fn rotate_left<T>(root: &mut Link<T>) {
                    *root = {
                        unsafe {
                            let mut root = root.unwrap();
                            let mut right = root.as_ref().right.unwrap();
                            root.as_mut().right = right.as_mut().left;
                            root.as_mut().fetch();
                            right.as_mut().left = Some(root);
                            right.as_mut().fetch();
                            Some(right)
                        }
                    };
                }
                if root.is_none() {
                    return None;
                }
                let d = diff_height(root);
                if d > 1 {
                    let left = &mut unsafe { root.unwrap().as_mut() }.left;
                    if diff_height(*left) < 0 {
                        rotate_left(left);
                    }
                    rotate_right(&mut root);
                } else if d < -1 {
                    let right = &mut unsafe { root.unwrap().as_mut() }.right;
                    if diff_height(*right) > 0 {
                        rotate_right(right);
                    }
                    rotate_left(&mut root);
                } else {
                    unsafe { root.unwrap().as_mut() }.fetch();
                }
                root
            }
            fn merge_with_root<T>(left: Link<T>, root: Link<T>, right: Link<T>) -> Link<T> {
                let d = height(left) - height(right);
                if d > 1 {
                    let raw_left = unsafe { left.unwrap().as_mut() };
                    raw_left.right = merge_with_root(raw_left.right, root, right);
                    balance(left)
                } else if d < -1 {
                    let raw_right = unsafe { right.unwrap().as_mut() };
                    raw_right.left = merge_with_root(left, root, raw_right.left);
                    balance(right)
                } else {
                    let raw_root = unsafe { root.unwrap().as_mut() };
                    raw_root.left = left;
                    raw_root.right = right;
                    balance(root)
                }
            }
            fn merge<T>(left: Link<T>, right: Link<T>) -> Link<T> {
                fn remove_max<T>(mut node: Link<T>) -> (Link<T>, Link<T>) {
                    let raw_node = unsafe { node.unwrap().as_mut() };
                    if raw_node.right.is_some() {
                        let (tmp, removed) = remove_max(raw_node.right);
                        raw_node.right = tmp;
                        node = balance(node);
                        (node, removed)
                    } else {
                        let removed = node;
                        node = raw_node.left;
                        (node, removed)
                    }
                }
                if left.is_none() {
                    right
                } else if right.is_none() {
                    left
                } else {
                    let (left, removed) = remove_max(left);
                    merge_with_root(left, removed, right)
                }
            }
            fn split<T>(root: Link<T>, index: usize) -> (Link<T>, Link<T>) {
                if root.is_none() {
                    return (None, None);
                }
                let (left, right) = {
                    let raw_root = unsafe { root.unwrap().as_mut() };
                    let left = raw_root.left;
                    let right = raw_root.right;
                    raw_root.left = None;
                    raw_root.right = None;
                    (left, right)
                };
                let left_len = len(left);
                if index < left_len {
                    let tmp = split(left, index);
                    (tmp.0, merge_with_root(tmp.1, root, right))
                } else if index > left_len {
                    let tmp = split(right, index - left_len - 1);
                    (merge_with_root(left, root, tmp.0), tmp.1)
                } else {
                    (left, merge_with_root(None, root, right))
                }
            }
            fn get<T>(root: Link<T>, index: usize) -> Link<T> {
                let raw_root = unsafe { root?.as_mut() };
                let left = raw_root.left;
                let right = raw_root.right;
                let left_len = len(left);
                if index < left_len {
                    get(left, index)
                } else if index > left_len {
                    get(right, index - left_len - 1)
                } else {
                    root
                }
            }
            fn bisect<T>(root: Link<T>, mut f: impl FnMut(&T) -> bool) -> usize {
                let node = if let Some(node) = root {
                    unsafe { node.as_ref() }
                } else {
                    return 0;
                };
                let left = node.left;
                let right = node.right;
                let left_len = len(left);
                if !f(&node.value) {
                    bisect(left, f)
                } else {
                    bisect(right, f) + left_len + 1
                }
            }
            #[allow(unused)]
            fn traverse<T>(
                node: Link<T>,
                mut preorder_f: impl FnMut(NodePtr<T>),
                mut inorder_f: impl FnMut(NodePtr<T>),
                mut postorder_f: impl FnMut(NodePtr<T>),
            ) {
                fn dfs<T>(
                    node: Link<T>,
                    preorder_f: &mut impl FnMut(NodePtr<T>),
                    inorder_f: &mut impl FnMut(NodePtr<T>),
                    postorder_f: &mut impl FnMut(NodePtr<T>),
                ) {
                    if let Some(node) = node {
                        let left = unsafe { node.as_ref() }.left;
                        let right = unsafe { node.as_ref() }.right;
                        preorder_f(node);
                        dfs(left, preorder_f, inorder_f, postorder_f);
                        inorder_f(node);
                        dfs(right, preorder_f, inorder_f, postorder_f);
                        postorder_f(node);
                    }
                }
                dfs(node, &mut preorder_f, &mut inorder_f, &mut postorder_f);
            }
            #[allow(unused)]
            #[inline]
            fn traverse_preorder<T>(node: Link<T>, f: impl FnMut(NodePtr<T>)) {
                traverse(node, f, |_| {}, |_| {});
            }
            #[allow(unused)]
            #[inline]
            fn traverse_inorder<T>(node: Link<T>, f: impl FnMut(NodePtr<T>)) {
                traverse(node, |_| {}, f, |_| {});
            }
            #[allow(unused)]
            #[inline]
            fn traverse_postorder<T>(node: Link<T>, f: impl FnMut(NodePtr<T>)) {
                traverse(node, |_| {}, |_| {}, f);
            }
            pub struct AvlTreeVec<T> {
                root: Link<T>,
            }
            impl<T> AvlTreeVec<T> {
                pub fn new() -> Self {
                    Self::default()
                }
                pub fn clear(&mut self) {
                    *self = Self::new();
                }
                pub fn len(&self) -> usize {
                    len(self.root)
                }
                pub fn is_empty(&self) -> bool {
                    self.len() == 0
                }
                pub fn get(&self, index: usize) -> Option<&T> {
                    Some(&unsafe { get(self.root, index)?.as_ref() }.value)
                }
                pub fn get_mut(&mut self, index: usize) -> Option<&mut T> {
                    Some(&mut unsafe { get(self.root, index)?.as_mut() }.value)
                }
                pub fn front(&self) -> Option<&T> {
                    self.get(0)
                }
                pub fn back(&self) -> Option<&T> {
                    self.get(self.len().checked_sub(1)?)
                }
                pub fn front_mut(&mut self) -> Option<&mut T> {
                    self.get_mut(0)
                }
                pub fn back_mut(&mut self) -> Option<&mut T> {
                    self.get_mut(self.len().checked_sub(1)?)
                }
                pub fn push_front(&mut self, value: T) {
                    self.insert(0, value);
                }
                pub fn push_back(&mut self, value: T) {
                    self.insert(self.len(), value);
                }
                pub fn pop_front(&mut self) -> Option<T> {
                    self.remove(0)
                }
                pub fn pop_back(&mut self) -> Option<T> {
                    self.remove(self.len().checked_sub(1)?)
                }
                pub fn insert(&mut self, index: usize, value: T) {
                    assert!(index <= self.len());
                    let new_node = Some(Node::new(value));
                    let (left, right) = split(self.root.take(), index);
                    self.root = merge_with_root(left, new_node, right);
                }
                pub fn remove(&mut self, index: usize) -> Option<T> {
                    (index < self.len()).then(|| {
                        let (left, right) = split(self.root.take(), index);
                        let (removed, right) = split(right, 1);
                        self.root = merge(left, right);
                        let boxed = unsafe { Box::from_raw(removed.unwrap().as_ptr()) };
                        boxed.value
                    })
                }
                pub fn append(&mut self, other: &mut Self) {
                    self.root = merge(self.root.take(), other.root.take())
                }
                pub fn split_off(&mut self, index: usize) -> Self {
                    assert!(index <= self.len());
                    let (left, right) = split(self.root.take(), index);
                    self.root = left;
                    Self { root: right }
                }
                pub fn bisect(&self, f: impl FnMut(&T) -> bool) -> usize {
                    bisect(self.root, f)
                }
                pub fn lower_bound(&self, value: &T) -> usize
                where
                    T: Ord,
                {
                    self.lower_bound_by(|e| e.cmp(value))
                }
                pub fn lower_bound_by(&self, mut f: impl FnMut(&T) -> Ordering) -> usize {
                    self.bisect(|e| f(e) == Ordering::Less)
                }
                pub fn lower_bound_by_key<K: Ord>(
                    &self,
                    k: &K,
                    mut f: impl FnMut(&T) -> K,
                ) -> usize {
                    self.lower_bound_by(|e| f(e).cmp(k))
                }
                pub fn upper_bound(&self, value: &T) -> usize
                where
                    T: Ord,
                {
                    self.upper_bound_by(|e| e.cmp(value))
                }
                pub fn upper_bound_by(&self, mut f: impl FnMut(&T) -> Ordering) -> usize {
                    self.bisect(|e| f(e) != Ordering::Greater)
                }
                pub fn upper_bound_by_key<K: Ord>(
                    &self,
                    k: &K,
                    mut f: impl FnMut(&T) -> K,
                ) -> usize {
                    self.upper_bound_by(|x| f(x).cmp(k))
                }
                pub fn iter(&self) -> Iter<'_, T> {
                    Iter::new(self.root)
                }
                pub fn iter_mut(&mut self) -> IterMut<'_, T> {
                    IterMut::new(self.root)
                }
            }
            impl<T> Default for AvlTreeVec<T> {
                fn default() -> Self {
                    Self { root: None }
                }
            }
            impl<T> Drop for AvlTreeVec<T> {
                fn drop(&mut self) {
                    traverse_postorder(self.root, |node| free(node));
                }
            }
            impl<T> Index<usize> for AvlTreeVec<T> {
                type Output = T;
                fn index(&self, index: usize) -> &Self::Output {
                    self.get(index).unwrap()
                }
            }
            impl<T> IndexMut<usize> for AvlTreeVec<T> {
                fn index_mut(&mut self, index: usize) -> &mut Self::Output {
                    self.get_mut(index).unwrap()
                }
            }
            impl<'a, T> IntoIterator for &'a AvlTreeVec<T> {
                type IntoIter = Iter<'a, T>;
                type Item = &'a T;
                fn into_iter(self) -> Self::IntoIter {
                    self.iter()
                }
            }
            impl<'a, T> IntoIterator for &'a mut AvlTreeVec<T> {
                type IntoIter = IterMut<'a, T>;
                type Item = &'a mut T;
                fn into_iter(self) -> Self::IntoIter {
                    self.iter_mut()
                }
            }
            impl<T> IntoIterator for AvlTreeVec<T> {
                type IntoIter = IntoIter<T>;
                type Item = T;
                fn into_iter(mut self) -> Self::IntoIter {
                    IntoIter::new(self.root.take())
                }
            }
            impl<T: PartialEq> PartialEq for AvlTreeVec<T> {
                fn eq(&self, other: &Self) -> bool {
                    self.iter().eq(other.iter())
                }
            }
            impl<T: Eq> Eq for AvlTreeVec<T> {}
            impl<T: PartialOrd> PartialOrd for AvlTreeVec<T> {
                fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
                    self.iter().partial_cmp(other.iter())
                }
            }
            impl<T: Ord> Ord for AvlTreeVec<T> {
                fn cmp(&self, other: &Self) -> Ordering {
                    self.iter().cmp(other.iter())
                }
            }
            impl<T: Hash> Hash for AvlTreeVec<T> {
                fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
                    self.iter().for_each(|item| item.hash(state));
                }
            }
            impl<T> Extend<T> for AvlTreeVec<T> {
                fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
                    iter.into_iter().for_each(|item| {
                        self.push_back(item);
                    });
                }
            }
            impl<'a, T: 'a + Copy> Extend<&'a T> for AvlTreeVec<T> {
                fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
                    self.extend(iter.into_iter().cloned());
                }
            }
            impl<T> FromIterator<T> for AvlTreeVec<T> {
                fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
                    let mut res = Self::new();
                    res.extend(iter);
                    res
                }
            }
            impl<T> From<Vec<T>> for AvlTreeVec<T> {
                fn from(v: Vec<T>) -> Self {
                    Self::from_iter(v)
                }
            }
            impl<T, const N: usize> From<[T; N]> for AvlTreeVec<T> {
                fn from(v: [T; N]) -> Self {
                    Self::from_iter(v)
                }
            }
            impl<T: Clone> Clone for AvlTreeVec<T> {
                fn clone(&self) -> Self {
                    Self::from_iter(self.iter().cloned())
                }
            }
            impl<T: Debug> Debug for AvlTreeVec<T> {
                fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
                    f.debug_list().entries(self.iter()).finish()
                }
            }
            struct IterBase<'a, T> {
                stack: Vec<NodePtr<T>>,
                stack_rev: Vec<NodePtr<T>>,
                phantom: PhantomData<&'a ()>,
            }
            impl<'a, T> IterBase<'a, T> {
                fn new(root: Link<T>) -> Self {
                    let mut iter = Self {
                        stack: vec![],
                        stack_rev: vec![],
                        phantom: PhantomData::default(),
                    };
                    iter.push_left(root);
                    iter.push_right(root);
                    iter
                }
                fn push_left(&mut self, mut node: Link<T>) {
                    while let Some(n) = node {
                        self.stack.push(n);
                        node = unsafe { n.as_ref() }.left;
                    }
                }
                fn push_right(&mut self, mut node: Link<T>) {
                    while let Some(n) = node {
                        self.stack_rev.push(n);
                        node = unsafe { n.as_ref() }.right;
                    }
                }
                fn next(&mut self) -> Option<NodePtr<T>> {
                    let node = self.stack.pop()?;
                    self.push_left(unsafe { node.as_ref() }.right);
                    Some(node)
                }
                fn next_back(&mut self) -> Option<NodePtr<T>> {
                    let node = self.stack_rev.pop()?;
                    self.push_right(unsafe { node.as_ref() }.left);
                    Some(node)
                }
            }
            pub struct Iter<'a, T>(IterBase<'a, T>);
            impl<'a, T: 'a> Iter<'a, T> {
                fn new(root: Link<T>) -> Self {
                    Self(IterBase::new(root))
                }
            }
            impl<'a, T: 'a> Iterator for Iter<'a, T> {
                type Item = &'a T;
                fn next(&mut self) -> Option<Self::Item> {
                    self.0.next().map(|node| &unsafe { node.as_ref() }.value)
                }
            }
            impl<'a, T: 'a> DoubleEndedIterator for Iter<'a, T> {
                fn next_back(&mut self) -> Option<Self::Item> {
                    self.0
                        .next_back()
                        .map(|node| &unsafe { node.as_ref() }.value)
                }
            }
            pub struct IterMut<'a, T>(IterBase<'a, T>);
            impl<'a, T: 'a> IterMut<'a, T> {
                fn new(root: Link<T>) -> Self {
                    Self(IterBase::new(root))
                }
            }
            impl<'a, T: 'a> Iterator for IterMut<'a, T> {
                type Item = &'a mut T;
                fn next(&mut self) -> Option<Self::Item> {
                    self.0
                        .next()
                        .map(|mut node| &mut unsafe { node.as_mut() }.value)
                }
            }
            impl<'a, T: 'a> DoubleEndedIterator for IterMut<'a, T> {
                fn next_back(&mut self) -> Option<Self::Item> {
                    self.0
                        .next_back()
                        .map(|mut node| &mut unsafe { node.as_mut() }.value)
                }
            }
            pub struct IntoIter<T> {
                iter: std::vec::IntoIter<T>,
            }
            impl<T> IntoIter<T> {
                fn new(root: Link<T>) -> Self {
                    let mut stack = Vec::with_capacity(len(root));
                    traverse_inorder(root, |node| {
                        let boxed = unsafe { Box::from_raw(node.as_ptr()) };
                        stack.push(boxed.value)
                    });
                    IntoIter {
                        iter: stack.into_iter(),
                    }
                }
            }
            impl<T> Iterator for IntoIter<T> {
                type Item = T;
                fn next(&mut self) -> Option<Self::Item> {
                    self.iter.next()
                }
            }
            impl<T> DoubleEndedIterator for IntoIter<T> {
                fn next_back(&mut self) -> Option<Self::Item> {
                    self.iter.next_back()
                }
            }
        }
    }
}
0