結果
| 問題 | No.649 ここでちょっとQK！ |
| ユーザー |
 ngtkana
|
| 提出日時 | 2023-11-23 10:31:38 |
| 言語 | Rust (1.77.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 285 ms / 3,000 ms |
| コード長 | 37,074 bytes |
| コンパイル時間 | 15,277 ms |
| コンパイル使用メモリ | 379,392 KB |
| 実行使用メモリ | 14,336 KB |
| 最終ジャッジ日時 | 2024-09-26 07:58:45 |
| 合計ジャッジ時間 | 21,044 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| 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 | 285 ms
5,376 KB |
| testcase_04 | AC | 133 ms
14,336 KB |
| testcase_05 | AC | 128 ms
14,336 KB |
| testcase_06 | AC | 133 ms
14,336 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 | 77 ms
7,040 KB |
| testcase_13 | AC | 84 ms
6,912 KB |
| testcase_14 | AC | 84 ms
6,784 KB |
| testcase_15 | AC | 91 ms
6,912 KB |
| testcase_16 | AC | 92 ms
7,552 KB |
| testcase_17 | AC | 104 ms
7,808 KB |
| testcase_18 | AC | 116 ms
8,448 KB |
| testcase_19 | AC | 130 ms
8,704 KB |
| testcase_20 | AC | 144 ms
9,216 KB |
| testcase_21 | AC | 151 ms
9,728 KB |
| testcase_22 | AC | 165 ms
10,368 KB |
| testcase_23 | AC | 167 ms
10,752 KB |
| testcase_24 | AC | 176 ms
11,264 KB |
| testcase_25 | AC | 192 ms
11,776 KB |
| testcase_26 | AC | 203 ms
12,416 KB |
| testcase_27 | AC | 1 ms
5,376 KB |
| testcase_28 | AC | 1 ms
5,376 KB |
| testcase_29 | AC | 2 ms
5,376 KB |
| testcase_30 | AC | 75 ms
7,040 KB |
| testcase_31 | AC | 81 ms
7,424 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:1005:13
|
1005 | pub use map::Multimap;
| ^^^^^^^^^^^^^
|
= note: `#[warn(unused_imports)]` on by default
warning: unused import: `map::MultimapOp`
--> src/main.rs:1006:13
|
1006 | 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 {
let x = *set.nth(k - 1);
set.remove(&x);
x
};
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;
}
// }}}