結果

問題 No.649 ここでちょっとQK!
ユーザー ngtkanangtkana
提出日時 2023-11-23 10:32:41
言語 Rust
(1.77.0 + proconio)
結果
AC  
実行時間 263 ms / 3,000 ms
コード長 36,941 bytes
コンパイル時間 14,719 ms
コンパイル使用メモリ 378,504 KB
実行使用メモリ 14,464 KB
最終ジャッジ日時 2024-09-26 07:59:08
合計ジャッジ時間 17,051 ms
ジャッジサーバーID
(参考情報)
judge2 / judge5
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 1 ms
5,248 KB
testcase_02 AC 1 ms
5,376 KB
testcase_03 AC 263 ms
5,376 KB
testcase_04 AC 121 ms
14,464 KB
testcase_05 AC 120 ms
14,336 KB
testcase_06 AC 128 ms
14,464 KB
testcase_07 AC 1 ms
5,376 KB
testcase_08 AC 1 ms
5,376 KB
testcase_09 AC 1 ms
5,376 KB
testcase_10 AC 1 ms
5,376 KB
testcase_11 AC 1 ms
5,376 KB
testcase_12 AC 68 ms
6,912 KB
testcase_13 AC 69 ms
6,912 KB
testcase_14 AC 67 ms
6,784 KB
testcase_15 AC 70 ms
7,040 KB
testcase_16 AC 69 ms
7,552 KB
testcase_17 AC 82 ms
7,936 KB
testcase_18 AC 90 ms
8,448 KB
testcase_19 AC 98 ms
8,832 KB
testcase_20 AC 103 ms
9,344 KB
testcase_21 AC 111 ms
9,728 KB
testcase_22 AC 115 ms
10,240 KB
testcase_23 AC 127 ms
10,752 KB
testcase_24 AC 139 ms
11,264 KB
testcase_25 AC 145 ms
11,904 KB
testcase_26 AC 157 ms
12,416 KB
testcase_27 AC 1 ms
5,376 KB
testcase_28 AC 2 ms
5,376 KB
testcase_29 AC 1 ms
5,376 KB
testcase_30 AC 63 ms
6,912 KB
testcase_31 AC 66 ms
7,296 KB
testcase_32 AC 1 ms
5,376 KB
testcase_33 AC 1 ms
5,376 KB
testcase_34 AC 1 ms
5,376 KB
testcase_35 AC 1 ms
5,376 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: unused import: `map::Multimap`
   --> src/main.rs:999:13
    |
999 |     pub use map::Multimap;
    |             ^^^^^^^^^^^^^
    |
    = note: `#[warn(unused_imports)]` on by default

warning: unused import: `map::MultimapOp`
    --> src/main.rs:1000:13
     |
1000 |     pub use map::MultimapOp;
     |             ^^^^^^^^^^^^^^^

ソースコード

diff #

use input::{input_array, input_vec};

fn main() {
    let [q, k] = input_array::<usize, 2>();
    let mut set = rb::Multiset::new();
    for _ in 0..q {
        let query = input_vec::<i64>();
        match query[0] {
            1 => {
                let x = query[1];
                set.insert(x);
            }
            2 => {
                let ans = if set.len() < k { -1 } else { set.remove_nth(k - 1) };
                println!("{}", ans);
            }
            _ => unreachable!(),
        }
    }
}

// input {{{
#[allow(dead_code)]
mod input {
    use std::cell::Cell;
    use std::convert::TryFrom;
    use std::io::stdin;
    use std::io::BufRead;
    use std::io::BufReader;
    use std::io::Lines;
    use std::io::Stdin;
    use std::str::FromStr;
    use std::sync::Mutex;
    use std::sync::Once;
    type Server = Mutex<Lines<BufReader<Stdin>>>;
    static ONCE: Once = Once::new();
    pub struct Lazy(Cell<Option<Server>>);
    unsafe impl Sync for Lazy {}
    fn line() -> String {
        static SYNCER: Lazy = Lazy(Cell::new(None));
        ONCE.call_once(|| {
            SYNCER
                .0
                .set(Some(Mutex::new(BufReader::new(stdin()).lines())));
        });
        unsafe {
            (*SYNCER.0.as_ptr())
                .as_ref()
                .unwrap()
                .lock()
                .unwrap()
                .next()
                .unwrap()
                .unwrap()
        }
    }
    pub trait ForceFromStr: FromStr {
        fn force_from_str(s: &str) -> Self;
    }
    impl<T, E> ForceFromStr for T
    where
        T: FromStr<Err = E>,
        E: std::fmt::Debug,
    {
        fn force_from_str(s: &str) -> Self {
            s.parse().unwrap()
        }
    }
    pub fn input_array<T: ForceFromStr, const N: usize>() -> [T; N]
    where
        T: std::fmt::Debug,
    {
        <[_; N]>::try_from(input_vec()).unwrap()
    }
    pub fn input_vec<T: ForceFromStr>() -> Vec<T> {
        line()
            .split_whitespace()
            .map(T::force_from_str)
            .collect::<Vec<_>>()
    }
    pub fn input<T: ForceFromStr>() -> T {
        T::force_from_str(&line())
    }
}
// }}}
// rb {{{
#[allow(dead_code)]
mod rb {
    mod balance {
        use core::fmt;
        use std::ops::Deref;
        use std::ops::DerefMut;
        use std::ptr::NonNull;
        #[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
        pub enum Color {
            Red,
            Black,
        }
        pub trait Balance: Sized {
            fn update(&mut self);
            fn push(&mut self);
            fn color(&mut self) -> &mut Color;
            fn parent(&mut self) -> &mut Option<Ptr<Self>>;
            fn left(&mut self) -> &mut Option<Ptr<Self>>;
            fn right(&mut self) -> &mut Option<Ptr<Self>>;
        }
        pub struct Tree<T: Balance> {
            pub root: Option<Ptr<T>>,
            pub black_height: u8,
        }
        impl<T: Balance> Tree<T> {
            pub fn new() -> Self {
                Self {
                    root: None,
                    black_height: 0,
                }
            }
            pub fn min(&self) -> Option<Ptr<T>> {
                let mut x = self.root?;
                while let Some(l) = *x.left() {
                    x = l;
                }
                Some(x)
            }
            pub fn max(&self) -> Option<Ptr<T>> {
                let mut x = self.root?;
                while let Some(r) = *x.right() {
                    x = r;
                }
                Some(x)
            }
            // Updates: the proper ancestors of `x` (i.e. `x` should be already updated)
            pub fn fix_red(&mut self, mut x: Ptr<T>) {
                while color(*x.parent()) == Color::Red {
                    let mut p = x.parent().unwrap();
                    let Some(mut pp) = p.parent() else {
                        p.update();
                        *p.color() = Color::Black;
                        self.black_height += 1;
                        return;
                    };
                    // Case 1: `p` is the left child.
                    if *pp.left() == Some(p) {
                        // Case 1.1: `pp` is a 5-node.
                        if color(*pp.right()) == Color::Red {
                            *p.color() = Color::Black;
                            *pp.color() = Color::Red;
                            *pp.right().unwrap().color() = Color::Black;
                            p.update();
                            pp.update();
                            x = pp;
                        }
                        // Case 1.2: `pp` is a splayed 4-node.
                        else if *p.right() == Some(x) {
                            rotate_left(p);
                            rotate_right(pp);
                            *x.color() = Color::Black;
                            *pp.color() = Color::Red;
                            p.update();
                            pp.update();
                            x.update();
                            break;
                        }
                        // Case 1.3: `pp` is a straight 4-node.
                        else {
                            rotate_right(pp);
                            *p.color() = Color::Black;
                            *pp.color() = Color::Red;
                            pp.update();
                            break;
                        }
                    }
                    // Case 2: `p` is the right child.
                    else {
                        // Case 2.1: `pp` is a 5-node.
                        if color(*pp.left()) == Color::Red {
                            *p.color() = Color::Black;
                            *pp.color() = Color::Red;
                            *pp.left().unwrap().color() = Color::Black;
                            p.update();
                            pp.update();
                            x = pp;
                        }
                        // Case 2.2: `pp` is a splayed 4-node.
                        else if *p.left() == Some(x) {
                            rotate_right(p);
                            rotate_left(pp);
                            *x.color() = Color::Black;
                            *pp.color() = Color::Red;
                            p.update();
                            pp.update();
                            x.update();
                            break;
                        }
                        // Case 2.3: `pp` is a straight 4-node.
                        else {
                            rotate_left(pp);
                            *p.color() = Color::Black;
                            *pp.color() = Color::Red;
                            pp.update();
                            break;
                        }
                    }
                }
                self.root = Some(x.update_ancestors());
            }
            // Updates: the proper ancestors of `x` (i.e. `x` should be already updated)
            pub fn fix_black(&mut self, black_violation: BlackViolation<T>) {
                let BlackViolation { p, mut x } = black_violation;
                loop {
                    if color(x) == Color::Red {
                        *x.unwrap().color() = Color::Black;
                        break;
                    }
                    let p = x.map_or(p, |mut x| *x.parent());
                    let Some(mut p) = p else {
                        self.black_height -= 1;
                        return;
                    };
                    // Case 1: `x` is the left child.
                    if *p.left() == x {
                        let mut s = p.right().unwrap();
                        if *s.color() == Color::Red {
                            rotate_left(p);
                            *p.color() = Color::Red;
                            *s.color() = Color::Black;
                            s = p.right().unwrap();
                        }
                        match (color(*s.left()), color(*s.right())) {
                            // Case 1.1: `s` is a 2-node.
                            (Color::Black, Color::Black) => {
                                *s.color() = Color::Red;
                                p.update();
                                x = Some(p);
                            }
                            // Case 1.2: `s` is a left-leaning 3-node.
                            (Color::Red, Color::Black) => {
                                let mut c = s.left().unwrap();
                                rotate_right(s);
                                rotate_left(p);
                                *c.color() = *p.color();
                                *p.color() = Color::Black;
                                s.update();
                                break;
                            }
                            // Case 1.3: `s` is a right-leaning 3-node, or a 4-node.
                            (_, Color::Red) => {
                                rotate_left(p);
                                *s.color() = *p.color();
                                *p.color() = Color::Black;
                                *s.right().unwrap().color() = Color::Black;
                                break;
                            }
                        }
                    }
                    // Case 2: `x` is the right child.
                    else {
                        let mut s = p.left().unwrap();
                        if *s.color() == Color::Red {
                            rotate_right(p);
                            *p.color() = Color::Red;
                            *s.color() = Color::Black;
                            s = p.left().unwrap();
                        }
                        match (color(*s.left()), color(*s.right())) {
                            // Case 2.1: `s` is a 2-node.
                            (Color::Black, Color::Black) => {
                                *s.color() = Color::Red;
                                p.update();
                                x = Some(p);
                            }
                            // Case 2.2: `s` os a right-leaning 3-node.
                            (Color::Black, Color::Red) => {
                                let mut c = s.right().unwrap();
                                rotate_left(s);
                                rotate_right(p);
                                *c.color() = *p.color();
                                *p.color() = Color::Black;
                                s.update();
                                break;
                            }
                            // Case 2.3: `s` is a left-leaning 3-node, or a 4-node.
                            (Color::Red, _) => {
                                rotate_right(p);
                                *s.color() = *p.color();
                                *p.color() = Color::Black;
                                *s.left().unwrap().color() = Color::Black;
                                break;
                            }
                        }
                    }
                }
                self.root = Some(match x {
                    None => {
                        p.unwrap().update();
                        p.unwrap().update_ancestors()
                    }
                    Some(x) => x.update_ancestors(),
                })
            }
            pub fn transplant(&mut self, mut place: Ptr<T>, new: Option<Ptr<T>>) {
                if let Some(mut p) = *place.parent() {
                    *(if *p.left() == Some(place) { p.left() } else { p.right() }) = new;
                } else {
                    self.root = new;
                }
                if let Some(mut new) = new {
                    *new.parent() = *place.parent();
                }
            }
        }
        impl<T: Balance> Clone for Tree<T> {
            fn clone(&self) -> Self {
                Self {
                    root: self.root,
                    black_height: self.black_height,
                }
            }
        }
        impl<T: Balance> Copy for Tree<T> {}
        pub struct BlackViolation<T: Balance> {
            pub p: Option<Ptr<T>>,
            pub x: Option<Ptr<T>>,
        }
        impl<T: Balance> PartialEq for BlackViolation<T> {
            fn eq(&self, other: &Self) -> bool {
                (self.p, self.x) == (other.p, other.x)
            }
        }
        impl<T: Balance> fmt::Debug for BlackViolation<T> {
            fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
                f.debug_struct("BlackViolation")
                    .field("p", &self.p)
                    .field("x", &self.x)
                    .finish()
            }
        }
        impl<T: Balance> Clone for BlackViolation<T> {
            fn clone(&self) -> Self {
                Self {
                    p: self.p,
                    x: self.x,
                }
            }
        }
        impl<T: Balance> Copy for BlackViolation<T> {}
        fn color<T: Balance>(x: Option<Ptr<T>>) -> Color {
            match x {
                None => Color::Black,
                Some(mut x) => *x.color(),
            }
        }
        fn rotate_left<T: Balance>(mut l: Ptr<T>) {
            let p = *l.parent();
            let mut r = l.right().unwrap();
            let c = *r.left();
            // Connect `p` and `r`.
            *r.parent() = p;
            if let Some(mut p) = p {
                *(if *p.left() == Some(l) { p.left() } else { p.right() }) = Some(r);
            }
            // Connect `r` and `l`.
            *l.parent() = Some(r);
            *r.left() = Some(l);
            // Connect `l` and `c`.
            if let Some(mut c) = c {
                *c.parent() = Some(l);
            }
            *l.right() = c;
        }
        fn rotate_right<T: Balance>(mut r: Ptr<T>) {
            let p = *r.parent();
            let mut l = r.left().unwrap();
            let c = *l.right();
            // Connect `p` and `l`.
            *l.parent() = p;
            if let Some(mut p) = p {
                *(if *p.left() == Some(r) { p.left() } else { p.right() }) = Some(l);
            }
            // Connect `l` and `r`.
            *r.parent() = Some(l);
            *l.right() = Some(r);
            // Connect `r` and `c`.
            if let Some(mut c) = c {
                *c.parent() = Some(r);
            }
            *r.left() = c;
        }
        pub struct Ptr<T>(NonNull<T>);
        impl<T: Balance> Ptr<T> {
            pub fn new(x: T) -> Self {
                Self(NonNull::from(Box::leak(Box::new(x))))
            }
            pub fn free(self) -> T {
                unsafe { *Box::from_raw(self.0.as_ptr()) }
            }
            // Returns the root
            pub fn update_ancestors(self) -> Self {
                let mut x = self;
                while let Some(mut p) = *x.parent() {
                    p.update();
                    x = p;
                }
                x
            }
            pub fn as_longlife_ref<'a>(self) -> &'a T {
                unsafe { self.0.as_ref() }
            }
            pub fn as_longlife_mut<'a>(mut self) -> &'a mut T {
                unsafe { self.0.as_mut() }
            }
        }
        impl<T> Clone for Ptr<T> {
            fn clone(&self) -> Self {
                *self
            }
        }
        impl<T> Copy for Ptr<T> {}
        impl<T> Deref for Ptr<T> {
            type Target = T;
            fn deref(&self) -> &Self::Target {
                unsafe { self.0.as_ref() }
            }
        }
        impl<T> DerefMut for Ptr<T> {
            fn deref_mut(&mut self) -> &mut Self::Target {
                unsafe { self.0.as_mut() }
            }
        }
        impl<T> fmt::Debug for Ptr<T> {
            fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
                write!(f, "{:02x}", self.0.as_ptr() as usize % 0x1000 / 0x10)
            }
        }
        impl<T> PartialEq for Ptr<T> {
            fn eq(&self, other: &Self) -> bool {
                std::ptr::eq(self.0.as_ptr(), other.0.as_ptr())
            }
        }
    }
    mod map {
        pub(crate) use crate::rb::balance::Balance;
        use crate::rb::balance::BlackViolation;
        use crate::rb::balance::Color;
        use crate::rb::balance::Ptr;
        use crate::rb::balance::Tree;
        use std::borrow::Borrow;
        use std::cmp::Ordering;
        use std::fmt;
        use std::marker::PhantomData;
        pub trait MultimapOp {
            type Value;
            type Acc;
            fn to_acc(value: &Self::Value) -> Self::Acc;
            fn join(
                lhs: Option<&Self::Acc>,
                center: &Self::Value,
                rhs: Option<&Self::Acc>,
            ) -> Self::Acc;
        }
        #[allow(dead_code)]
        pub struct Node<K, O: MultimapOp> {
            key: K,
            value: O::Value,
            acc: O::Acc,
            parent: Option<Ptr<Node<K, O>>>,
            left: Option<Ptr<Node<K, O>>>,
            right: Option<Ptr<Node<K, O>>>,
            len: usize,
            color: Color,
        }
        impl<K: Ord, O: MultimapOp> Node<K, O> {
            pub fn new(key: K, value: O::Value, color: Color) -> Self {
                Self {
                    key,
                    acc: O::to_acc(&value),
                    value,
                    parent: None,
                    left: None,
                    right: None,
                    len: 1,
                    color,
                }
            }
        }
        fn len<K, O: MultimapOp>(node: Option<Ptr<Node<K, O>>>) -> usize {
            node.as_ref().map_or(0, |node| node.len)
        }
        fn acc<K, O: MultimapOp>(node: &Option<Ptr<Node<K, O>>>) -> Option<&O::Acc> {
            node.as_ref().map(|node| &node.acc)
        }
        impl<K, O: MultimapOp> Balance for Node<K, O> {
            fn update(&mut self) {
                self.len = len(self.left) + 1 + len(self.right);
                self.acc = O::join(acc(&self.left), &self.value, acc(&self.right));
            }
            fn push(&mut self) {}
            fn color(&mut self) -> &mut Color {
                &mut self.color
            }
            fn parent(&mut self) -> &mut Option<Ptr<Self>> {
                &mut self.parent
            }
            fn left(&mut self) -> &mut Option<Ptr<Self>> {
                &mut self.left
            }
            fn right(&mut self) -> &mut Option<Ptr<Self>> {
                &mut self.right
            }
        }
        impl<K: Ord, O: MultimapOp> Ptr<Node<K, O>> {
            pub fn next(self) -> Option<Self> {
                let mut x = self;
                if let Some(r) = *x.right() {
                    x = r;
                    while let Some(l) = *x.left() {
                        x = l;
                    }
                    Some(x)
                } else {
                    while let Some(mut p) = *x.parent() {
                        if *p.left() == Some(x) {
                            return Some(p);
                        }
                        x = p;
                    }
                    None
                }
            }
            pub fn prev(self) -> Option<Self> {
                let mut x = self;
                if let Some(l) = *x.left() {
                    x = l;
                    while let Some(r) = *x.right() {
                        x = r;
                    }
                    Some(x)
                } else {
                    while let Some(mut p) = *x.parent() {
                        if *p.right() == Some(x) {
                            return Some(p);
                        }
                        x = p;
                    }
                    None
                }
            }
        }
        pub struct MultimapSeg<K, O: MultimapOp> {
            tree: Tree<Node<K, O>>,
        }
        impl<K: Ord, O: MultimapOp> MultimapSeg<K, O> {
            pub fn new() -> Self {
                Self { tree: Tree::new() }
            }
            pub fn len(&self) -> usize {
                len(self.tree.root)
            }
            pub fn is_empty(&self) -> bool {
                self.tree.root.is_none()
            }
            pub fn iter(&self) -> SegmapIter<'_, K, O> {
                SegmapIter {
                    start: self.tree.min(),
                    end: self.tree.max(),
                    len: self.len(),
                    marker: PhantomData,
                }
            }
            pub fn nth(&self, n: usize) -> (&K, &O::Value) {
                let x = self.nth_ptr(n).as_longlife_ref();
                (&x.key, &x.value)
            }
            pub fn nth_mut(&mut self, n: usize) -> (&K, &mut O::Value) {
                let x = self.nth_ptr(n).as_longlife_mut();
                (&x.key, &mut x.value)
            }
            pub fn binary_search<Q: ?Sized>(&self, key: &Q) -> Result<(&O::Value, usize), usize>
            where
                K: Ord + Borrow<Q>,
                Q: Ord,
            {
                self.binary_search_ptr(key)
                    .map(|(x, i)| (&x.as_longlife_ref().value, i))
            }
            pub fn partition_point(&self, mut f: impl FnMut(&K) -> bool) -> usize {
                let Some(mut x) = self.tree.root else { return 0 };
                let mut index = 0;
                loop {
                    x = if f(&x.key) {
                        index += len(x.left) + 1;
                        let Some(right) = x.right else {
                            break;
                        };
                        right
                    } else {
                        let Some(left) = x.left else {
                            break;
                        };
                        left
                    };
                }
                index
            }
            pub fn lower_bound(&self, key: &K) -> usize {
                self.partition_point(|x| x < key)
            }
            pub fn upper_bound(&self, key: &K) -> usize {
                self.partition_point(|x| x <= key)
            }
            pub fn insert(&mut self, key: K, value: O::Value) {
                let mut new = Ptr::new(Node::new(key, value, Color::Red));
                let Some(mut x) = self.tree.root else {
                    new.color = Color::Black;
                    self.tree.root = Some(new);
                    self.tree.black_height = 1;
                    return;
                };
                let key = &new.key;
                loop {
                    match key.cmp(&x.key) {
                        Ordering::Less | Ordering::Equal => {
                            if let Some(left) = x.left {
                                x = left;
                            } else {
                                new.parent = Some(x);
                                x.left = Some(new);
                                break;
                            }
                        }
                        Ordering::Greater => {
                            if let Some(right) = x.right {
                                x = right;
                            } else {
                                new.parent = Some(x);
                                x.right = Some(new);
                                break;
                            }
                        }
                    }
                }
                if x.color == Color::Red {
                    self.tree.fix_red(new);
                } else {
                    new.update_ancestors();
                }
            }
            pub fn remove<Q: ?Sized>(&mut self, key: &Q) -> Option<(K, O::Value)>
            where
                K: Ord + Borrow<Q>,
                Q: Ord,
            {
                let x = self.binary_search_ptr(key).ok()?.0;
                self.remove_ptr(x);
                let x = x.free();
                Some((x.key, x.value))
            }
            pub fn remove_nth(&mut self, n: usize) -> (K, O::Value) {
                let x = self.nth_ptr(n);
                self.remove_ptr(x);
                let x = x.free();
                (x.key, x.value)
            }
            fn nth_ptr(&self, mut n: usize) -> Ptr<Node<K, O>> {
                assert!(
                    n < self.len(),
                    "Index out of range: n = {n}, while len = {}",
                    self.len()
                );
                let mut x = self.tree.root.unwrap();
                loop {
                    let left_len = len(x.left);
                    x = match n.cmp(&left_len) {
                        Ordering::Less => x.left.unwrap(),
                        Ordering::Equal => break,
                        Ordering::Greater => {
                            n -= left_len + 1;
                            x.right.unwrap()
                        }
                    };
                }
                x
            }
            pub fn binary_search_ptr<Q: ?Sized>(
                &self,
                key: &Q,
            ) -> Result<(Ptr<Node<K, O>>, usize), usize>
            where
                K: Ord + Borrow<Q>,
                Q: Ord,
            {
                let mut x = self.tree.root.ok_or(0usize)?;
                let mut index = 0;
                loop {
                    x = match key.cmp(x.key.borrow()) {
                        Ordering::Less => x.left.ok_or(index)?,
                        Ordering::Greater => {
                            index += len(x.left) + 1;
                            x.right.ok_or(index)?
                        }
                        Ordering::Equal => break,
                    }
                }
                Ok((x, index + len(x.left)))
            }
            fn remove_ptr(&mut self, x: Ptr<Node<K, O>>) {
                let needs_fix;
                let black_vio;
                match (x.left, x.right) {
                    (Some(_), Some(top)) => {
                        let mut next = top;
                        while let Some(left) = next.left {
                            next = left;
                        }
                        needs_fix = next.color == Color::Black;
                        next.left = x.left;
                        x.left.unwrap().parent = Some(next);
                        next.color = x.color;
                        if top == next {
                            black_vio = BlackViolation {
                                p: Some(next),
                                x: next.right,
                            };
                            self.tree.transplant(x, Some(next));
                        } else {
                            black_vio = BlackViolation {
                                p: next.parent,
                                x: next.right,
                            };
                            self.tree.transplant(next, next.right);
                            next.right = x.right;
                            if let Some(mut r) = next.right {
                                r.parent = Some(next);
                            }
                            self.tree.transplant(x, Some(next));
                        }
                    }
                    (None, Some(_)) => {
                        needs_fix = x.color == Color::Black;
                        black_vio = BlackViolation {
                            p: x.parent,
                            x: x.right,
                        };
                        self.tree.transplant(x, x.right);
                    }
                    (_, None) => {
                        needs_fix = x.color == Color::Black;
                        black_vio = BlackViolation {
                            p: x.parent,
                            x: x.left,
                        };
                        self.tree.transplant(x, x.left);
                    }
                }
                if needs_fix {
                    self.tree.fix_black(black_vio);
                } else if let Some(mut p) = black_vio.p {
                    p.update();
                    p.update_ancestors();
                }
            }
        }
        impl<K: Ord, O: MultimapOp> Default for MultimapSeg<K, O> {
            fn default() -> Self {
                Self::new()
            }
        }
        impl<'a, K: Ord, O: MultimapOp> IntoIterator for &'a MultimapSeg<K, O> {
            type IntoIter = SegmapIter<'a, K, O>;
            type Item = (&'a K, &'a O::Value);
            fn into_iter(self) -> Self::IntoIter {
                self.iter()
            }
        }
        pub struct SegmapIter<'a, K: Ord, O: MultimapOp> {
            start: Option<Ptr<Node<K, O>>>,
            end: Option<Ptr<Node<K, O>>>,
            len: usize,
            marker: PhantomData<&'a (K, O)>,
        }
        impl<'a, K: Ord, O: MultimapOp> Iterator for SegmapIter<'a, K, O> {
            type Item = (&'a K, &'a O::Value);
            fn next(&mut self) -> Option<Self::Item> {
                if self.len == 0 {
                    return None;
                }
                let x = self.start.unwrap();
                self.start = x.next();
                self.len -= 1;
                let x = x.as_longlife_ref();
                Some((&x.key, &x.value))
            }
            fn size_hint(&self) -> (usize, Option<usize>) {
                (self.len, Some(self.len))
            }
        }
        impl<'a, K: Ord, O: MultimapOp> DoubleEndedIterator for SegmapIter<'a, K, O> {
            fn next_back(&mut self) -> Option<Self::Item> {
                if self.len == 0 {
                    return None;
                }
                let x = self.end.unwrap();
                self.end = x.prev();
                self.len -= 1;
                let x = x.as_longlife_ref();
                Some((&x.key, &x.value))
            }
        }
        impl<'a, K: Ord, O: MultimapOp> ExactSizeIterator for SegmapIter<'a, K, O> {}
        struct Nop<T>(PhantomData<T>);
        impl<T> MultimapOp for Nop<T> {
            type Acc = ();
            type Value = T;
            fn to_acc(_value: &Self::Value) -> Self::Acc {}
            fn join(
                _lhs: Option<&Self::Acc>,
                _center: &Self::Value,
                _rhs: Option<&Self::Acc>,
            ) -> Self::Acc {
            }
        }
        pub struct Multimap<K, V> {
            segmap: MultimapSeg<K, Nop<V>>,
        }
        impl<K: Ord, V> Multimap<K, V> {
            pub fn new() -> Self {
                Self {
                    segmap: MultimapSeg::new(),
                }
            }
            pub fn len(&self) -> usize {
                self.segmap.len()
            }
            pub fn is_empty(&self) -> bool {
                self.segmap.is_empty()
            }
            pub fn iter(&self) -> MultimapIter<'_, K, V> {
                MultimapIter {
                    iter: self.segmap.iter(),
                }
            }
            pub fn nth(&self, n: usize) -> (&K, &V) {
                self.segmap.nth(n)
            }
            pub fn binary_search<Q: ?Sized>(&self, key: &Q) -> Result<(&V, usize), usize>
            where
                K: Ord + Borrow<Q>,
                Q: Ord,
            {
                self.segmap.binary_search(key)
            }
            pub fn partition_point(&self, f: impl FnMut(&K) -> bool) -> usize {
                self.segmap.partition_point(f)
            }
            pub fn lower_bound(&self, key: &K) -> usize {
                self.segmap.lower_bound(key)
            }
            pub fn upper_bound(&self, key: &K) -> usize {
                self.segmap.upper_bound(key)
            }
            pub fn insert(&mut self, key: K, value: V) {
                self.segmap.insert(key, value)
            }
            pub fn remove<Q: ?Sized>(&mut self, key: &Q) -> Option<(K, V)>
            where
                K: Ord + Borrow<Q>,
                Q: Ord,
            {
                self.segmap.remove(key)
            }
            pub fn remove_nth(&mut self, n: usize) -> (K, V) {
                self.segmap.remove_nth(n)
            }
        }
        impl<K: Ord, V> Default for Multimap<K, V> {
            fn default() -> Self {
                Self::new()
            }
        }
        impl<K: Ord + fmt::Debug, V: fmt::Debug> fmt::Debug for Multimap<K, V> {
            fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
                f.debug_map().entries(self.iter()).finish()
            }
        }
        impl<'a, K: Ord, V> IntoIterator for &'a Multimap<K, V> {
            type IntoIter = MultimapIter<'a, K, V>;
            type Item = (&'a K, &'a V);
            fn into_iter(self) -> Self::IntoIter {
                self.iter()
            }
        }
        pub struct MultimapIter<'a, K: Ord, V> {
            iter: SegmapIter<'a, K, Nop<V>>,
        }
        impl<'a, K: Ord, V> Iterator for MultimapIter<'a, K, V> {
            type Item = (&'a K, &'a V);
            fn next(&mut self) -> Option<Self::Item> {
                self.iter.next()
            }
            fn size_hint(&self) -> (usize, Option<usize>) {
                self.iter.size_hint()
            }
        }
        impl<'a, K: Ord, V> DoubleEndedIterator for MultimapIter<'a, K, V> {
            fn next_back(&mut self) -> Option<Self::Item> {
                self.iter.next_back()
            }
        }
        impl<'a, K: Ord, V> ExactSizeIterator for MultimapIter<'a, K, V> {}
        pub struct Multiset<K> {
            map: Multimap<K, ()>,
        }
        impl<K: Ord> Multiset<K> {
            pub fn new() -> Self {
                Self {
                    map: Multimap::new(),
                }
            }
            pub fn len(&self) -> usize {
                self.map.len()
            }
            pub fn is_empty(&self) -> bool {
                self.map.is_empty()
            }
            pub fn iter(&self) -> MultisetIter<'_, K> {
                MultisetIter {
                    iter: self.map.iter(),
                }
            }
            pub fn nth(&self, n: usize) -> &K {
                self.map.nth(n).0
            }
            pub fn binary_search<Q: ?Sized>(&self, key: &Q) -> Result<usize, usize>
            where
                K: Ord + Borrow<Q>,
                Q: Ord,
            {
                self.map.binary_search(key).map(|(_, i)| i)
            }
            pub fn partition_point(&self, f: impl FnMut(&K) -> bool) -> usize {
                self.map.partition_point(f)
            }
            pub fn lower_bound(&self, key: &K) -> usize {
                self.map.lower_bound(key)
            }
            pub fn upper_bound(&self, key: &K) -> usize {
                self.map.upper_bound(key)
            }
            pub fn insert(&mut self, key: K) {
                self.map.insert(key, ())
            }
            pub fn remove<Q: ?Sized>(&mut self, key: &Q) -> Option<K>
            where
                K: Ord + Borrow<Q>,
                Q: Ord,
            {
                self.map.remove(key).map(|(k, _)| k)
            }
            pub fn remove_nth(&mut self, n: usize) -> K {
                self.map.remove_nth(n).0
            }
        }
        impl<K: Ord> Default for Multiset<K> {
            fn default() -> Self {
                Self::new()
            }
        }
        impl<K: Ord + fmt::Debug> fmt::Debug for Multiset<K> {
            fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
                f.debug_set().entries(self.iter()).finish()
            }
        }
        impl<'a, K: Ord> IntoIterator for &'a Multiset<K> {
            type IntoIter = MultisetIter<'a, K>;
            type Item = &'a K;
            fn into_iter(self) -> Self::IntoIter {
                self.iter()
            }
        }
        pub struct MultisetIter<'a, K: Ord> {
            iter: MultimapIter<'a, K, ()>,
        }
        impl<'a, K: Ord> Iterator for MultisetIter<'a, K> {
            type Item = &'a K;
            fn next(&mut self) -> Option<Self::Item> {
                self.iter.next().map(|(k, _)| k)
            }
            fn size_hint(&self) -> (usize, Option<usize>) {
                self.iter.size_hint()
            }
        }
        impl<'a, K: Ord> DoubleEndedIterator for MultisetIter<'a, K> {
            fn next_back(&mut self) -> Option<Self::Item> {
                self.iter.next_back().map(|(k, _)| k)
            }
        }
        impl<'a, K: Ord> ExactSizeIterator for MultisetIter<'a, K> {}
    }
    pub use map::Multimap;
    pub use map::MultimapOp;
    pub use map::Multiset;
}
// }}}
0