結果
問題 | No.649 ここでちょっとQK! |
ユーザー | ngtkana |
提出日時 | 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; | ^^^^^^^^^^^^^^^
ソースコード
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; } // }}}