結果
問題 | No.2421 entersys? |
ユーザー |
|
提出日時 | 2023-08-12 14:35:36 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 965 ms / 3,000 ms |
コード長 | 33,105 bytes |
コンパイル時間 | 15,416 ms |
コンパイル使用メモリ | 377,864 KB |
実行使用メモリ | 91,388 KB |
最終ジャッジ日時 | 2024-11-19 20:17:03 |
合計ジャッジ時間 | 32,650 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 28 |
コンパイルメッセージ
warning: unnecessary parentheses around block return value --> src/main.rs:829:9 | 829 | (base.0 + (cmp.0 == Less) as usize..base.1 + (cmp.1 != Greater) as usize) | ^ ^ | = note: `#[warn(unused_parens)]` on by default help: remove these parentheses | 829 - (base.0 + (cmp.0 == Less) as usize..base.1 + (cmp.1 != Greater) as usize) 829 + base.0 + (cmp.0 == Less) as usize..base.1 + (cmp.1 != Greater) as usize | warning: unused variable: `i` --> src/main.rs:52:14 | 52 | |&(a,i):&(Self::Type,usize), &b:&Self::F| a + b | ^ help: if this is intentional, prefix it with an underscore: `_i` | = note: `#[warn(unused_variables)]` on by default warning: variable does not need to be mutable --> src/main.rs:190:13 | 190 | let mut left = match range.start_bound() { | ----^^^^ | | | help: remove this `mut` | = note: `#[warn(unused_mut)]` on by default warning: variable does not need to be mutable --> src/main.rs:195:13 | 195 | let mut right = match range.end_bound() { | ----^^^^^ | | | help: remove this `mut`
ソースコード
fn main() {let mut sc = Scanner::new();let n = sc.usize();let mut times = vec![];let mut xlr = vec![];for _ in 0..n {let x = sc.input::<String>();let l = sc.usize();let r = sc.usize();xlr.push((x, l, r));times.push(l);times.push(r);}let q = sc.usize();let mut queries : Vec<(u8, String, usize, usize)> = vec![];for _ in 0..q {let t = sc.u8();match t {1 => {let x = sc.input::<String>();let time = sc.usize();queries.push((t, x, time, 0));times.push(time);}2 => {let time = sc.usize();queries.push((t, "".to_string(), time, 0));times.push(time);}3 => {let x = sc.input::<String>();let l = sc.usize();let r = sc.usize();queries.push((t, x, l, r));times.push(l);times.push(r);}_ => unreachable!()}}times.sort(); times.dedup();def_map_monoid!(M,i64,i64,0,|&a:&Self::Type, &b:&Self::Type| a.max(b),|&a:&Self::F,&b:&Self::F| a + b,|&(a,i):&(Self::Type,usize), &b:&Self::F| a + b);let mut id = BTreeMap::new();let mut now = 0;let mut sets = vec![];let mut seg = LazySegmentTree::<M>::new(times.len());for (x, l, r) in xlr {let l = times.lower_bound(&l);let r = times.lower_bound(&r);seg.update(l..=r, 1);if !id.contains_key(&x) {id.insert(x.clone(), now);now += 1;sets.push(RangeSet::new(true));}let id = id[&x];sets[id].insert_range(l as i64 ..=r as i64);}for i in 0..q {match queries[i] {(1, ref x, time, _) => {let time = times.lower_bound(&time);if !id.contains_key(x) {println!("No");continue;}let id = id[x];if sets[id].contains(time as i64) {println!("Yes");} else {println!("No");}}(2, _, time, _) => {let time = times.lower_bound(&time);let ans = seg.fold(time..=time);println!("{}", ans);}(3, ref x, l, r) => {let l = times.lower_bound(&l);let r = times.lower_bound(&r);if !id.contains_key(x) {id.insert(x.clone(), now);now += 1;sets.push(RangeSet::new(true));}let id = id[x];seg.update(l..=r, 1);sets[id].insert_range(l as i64..=r as i64);}_ => unreachable!()}}}struct RangeSet {ranges: std::collections::BTreeSet<(i64, i64)>,len: i64,merge_adjacent_range_flag: bool}#[allow(dead_code)]impl RangeSet {fn new(merge_adjacent_range_flag: bool) -> Self {Self { ranges: std::collections::BTreeSet::new(), len:0, merge_adjacent_range_flag }}fn contains(&self, x:i64) -> bool {self.contains_range(x..=x)}fn contains_range<R:std::ops::RangeBounds<i64>>(&self, range:R) -> bool {let left = match range.start_bound() {std::ops::Bound::Unbounded => unreachable!(),std::ops::Bound::Included(&l) => l,_ => unreachable!()};let right = match range.end_bound() {std::ops::Bound::Unbounded => unreachable!(),std::ops::Bound::Included(&x) => x + 1,std::ops::Bound::Excluded(&x) => x,};if let Some(&(l2, r2)) = self.ranges.range((left,left)..).next() {if l2 <= left && right <= r2 { return true; }}if let Some(&(l2, r2)) = self.ranges.range(..(left,left)).next_back() {if l2 <= left && right <= r2 { return true; }}false}fn insert(&mut self, x:i64) -> (i64, i64) {self.insert_range(x..=x)}fn insert_range<R:std::ops::RangeBounds<i64>>(&mut self, range:R) -> (i64, i64) {let mut left = match range.start_bound() {std::ops::Bound::Unbounded => unreachable!(),std::ops::Bound::Included(&l) => l,_ => unreachable!()};let mut right = match range.end_bound() {std::ops::Bound::Unbounded => unreachable!(),std::ops::Bound::Included(&x) => x + 1,std::ops::Bound::Excluded(&x) => x,};let mut erase = vec![];for &(l, r) in self.ranges.range((left,left)..=(right,right)) {left = left.min(l);right = right.max(r);erase.push((l, r));}if let Some(&prev) = self.ranges.range(..(left,std::i64::MIN)).next_back() {if left < prev.1 + if self.merge_adjacent_range_flag {1} else {0} { left = left.min(prev.0); right = right.max(prev.1); erase.push(prev);}}if let Some(&next) = self.ranges.range((right, std::i64::MIN)..).next() {if right > next.0 - if self.merge_adjacent_range_flag {1} else {0} { left = left.min(next.0); right = right.max(next.1); erase.push(next); }}for e in erase { self.ranges.remove(&e); self.len -= e.1 - e.0 }self.ranges.insert((left, right));self.len += right - left;(left, right)}fn remove(&mut self, x:i64) -> () {self.remove_range(x..=x);}fn remove_range<R:std::ops::RangeBounds<i64>>(&mut self, range:R) -> () {let mut left = match range.start_bound() {std::ops::Bound::Unbounded => unreachable!(),std::ops::Bound::Included(&l) => l,_ => unreachable!()};let mut right = match range.end_bound() {std::ops::Bound::Unbounded => unreachable!(),std::ops::Bound::Included(&x) => x + 1,std::ops::Bound::Excluded(&x) => x,};let mut erase = vec![];let mut add = vec![];for &(l, r) in self.ranges.range((left,left)..=(right,right)) {if right < r { add.push((right, r)); }if l < left { add.push((l, left)); }erase.push((l, r));}if let Some(&prev) = self.ranges.range(..(left,std::i64::MIN)).next_back() {if left < prev.1 + if self.merge_adjacent_range_flag {1} else {0} {if prev.0 < left { add.push((prev.0, left)); }if right < prev.1 { add.push((right, prev.1)); }erase.push(prev);}}if let Some(&next) = self.ranges.range((right, std::i64::MIN)..).next() {if right > next.0 - if self.merge_adjacent_range_flag {1} else {0} {if next.0 < left { add.push((next.0, left)); }if right < next.1 { add.push((right, next.1)); }erase.push(next);}}for e in erase { self.ranges.remove(&e); self.len -= e.1 - e.0 }for a in add { self.ranges.insert(a); self.len += a.1 - a.0 }}fn ranges_count(&self) -> usize {self.ranges.len()}fn len(&self) -> i64 {self.len}fn iter(&self) -> std::collections::btree_set::Iter<'_, (i64, i64)> {self.ranges.iter()}fn mex(&self, mut x:i64) -> i64 {if let Some(prev) = self.ranges.range(..=(x,std::i64::MAX)).next_back() {if x <= prev.0 { x = prev.1 + 1; }}x}}#[macro_export]macro_rules! def_map_monoid {($m:ident, $t1:ty, $t2:ty, $id:expr, $op:expr, $merge:expr, $eval:expr) => {pub struct $m;impl MapMonoid for $m {type Type = $t1;type F = $t2;fn identity() -> Self::Type { $id }fn operator(x:&Self::Type, y:&Self::Type) -> Self::Type { $op(x, y) }fn merge(x:&Option<Self::F>, y:&Option<Self::F>) -> Option<Self::F> {match (x, y) {(None, None) => None,(Some(x), Some(y)) => Some($merge(x, y)),(&x, None) => x,(None, &y) => y}}fn eval(x:&(Self::Type, usize), y:&Self::F) -> Self::Type {$eval(x, y)}}};}pub trait MapMonoid {type Type: Copy + Clone + std::fmt::Debug;type F: Copy + Clone + std::fmt::Debug;fn identity() -> Self::Type;fn operator(a: &Self::Type, b: &Self::Type) -> Self::Type;fn merge(a: &Option<Self::F>, b: &Option<Self::F>) -> Option<Self::F>;fn eval(a: &(Self::Type, usize), b: &Self::F) -> Self::Type;}struct LazySegmentTree<T: MapMonoid> {n: usize,seg: Vec<(T::Type, usize)>,lazy: Vec<Option<T::F>>,}#[allow(unused)]impl<T: MapMonoid> LazySegmentTree<T> {pub fn new(n: usize) -> Self {let mut seg = vec![(T::identity(), 1); 2*n+1];for i in (1..n).rev() { seg[i].1 = seg[2*i].1 + seg[2*i+1].1; }Self { n, seg: seg, lazy: vec![None; 2 * n + 1] }}pub fn from(s: &[T::Type]) -> Self {let n = s.len();let mut seg = vec![(T::identity(), 1); 2 * n + 1];for (i, &si) in s.iter().enumerate() { seg[i + n].0 = si; }for i in (1..n).rev() {seg[i].0 = T::operator(&seg[2 * i].0, &seg[2 * i + 1].0);seg[i].1 = &seg[2 * i].1 + &seg[2 * i + 1].1;}LazySegmentTree { n, seg, lazy: vec![None; 2 * n + 1] }}fn eval(&mut self, i: usize) -> T::Type {if let Some(x) = self.lazy[i] {T::eval(&self.seg[i], &x)} else {self.seg[i].0}}fn propagate_at(&mut self, i: usize) {self.seg[i] = (self.eval(i), self.seg[i].1);self.lazy[i*2] = T::merge(&self.lazy[i * 2], &self.lazy[i]);self.lazy[i*2 + 1] = T::merge(&self.lazy[i * 2 + 1], &self.lazy[i]);self.lazy[i] = None;}fn propagate_above(&mut self, i: usize) {let height = 63u32.saturating_sub(i.leading_zeros());for h in (1..=height).rev() {self.propagate_at(i >> h);}}fn recalc_above(&mut self, mut i: usize) {while i > 0 {i /= 2;let left = self.eval(i * 2);let right = self.eval(i * 2 + 1);self.seg[i].0 = T::operator(&left, &right);}}fn _update(&mut self, mut l: usize, mut r: usize, x: T::F) {let l0 = l / (l & l.wrapping_neg());let r0 = r / (r & r.wrapping_neg()) - 1;self.propagate_above(l0);self.propagate_above(r0);while l < r {if l % 2 == 1 {self.lazy[l] = T::merge(&self.lazy[l], &Some(x));l += 1;}if r % 2 == 1 {r -= 1;self.lazy[r] = T::merge(&self.lazy[r], &Some(x));}l /= 2;r /= 2;}self.recalc_above(l0);self.recalc_above(r0);}pub fn update<R: std::ops::RangeBounds<usize>>(&mut self, range: R, x: T::F) {let l = self.n + match range.start_bound() {std::ops::Bound::Unbounded => 0,std::ops::Bound::Included(&l) => l,_ => unreachable!()};let r = self.n + match range.end_bound() {std::ops::Bound::Unbounded => self.n,std::ops::Bound::Included(&x) => x + 1,std::ops::Bound::Excluded(&x) => x,};self._update(l, r, x)}fn _fold(&mut self, mut l: usize, mut r: usize) -> T::Type {let mut left = T::identity();let mut right = T::identity();self.propagate_above(l / (l & l.wrapping_neg()));self.propagate_above(r / (r & r.wrapping_neg()) - 1);while l < r {if l % 2 == 1 {left = T::operator(&left, &self.eval(l));l += 1;}if r % 2 == 1 {r -= 1;right = T::operator(&self.eval(r), &right);}l /= 2;r /= 2;}T::operator(&left, &right)}pub fn fold<R: std::ops::RangeBounds<usize>>(&mut self, range: R) -> T::Type {let l = self.n + match range.start_bound() {std::ops::Bound::Unbounded => 0,std::ops::Bound::Included(&l) => l,_ => unreachable!()};let r = self.n + match range.end_bound() {std::ops::Bound::Unbounded => self.n,std::ops::Bound::Included(&x) => x + 1,std::ops::Bound::Excluded(&x) => x,};self._fold(l, r)}pub fn get(&mut self, index: usize) -> T::Type { self.fold(index..=index) }}struct Scanner { s : std::collections::VecDeque<String> } #[allow(unused)] impl Scanner { fn new() -> Self { use std::io::Read; let mut s = String::new(); std::io::stdin().read_to_string(&mut s).unwrap(); Self { s : s.split_whitespace().map(|s| s.to_string()).collect() } } fn reload(&mutself) -> () { use std::io::Read; let mut s = String::new(); std::io::stdin().read_to_string(&mut s).unwrap(); self.s = s.split_whitespace().map(|s| s.to_string()).collect(); } fn usize(&mut self) -> usize { self.input() } fn usize1(&mut self) -> usize { self.input::<usize>() - 1 } fnisize(&mut self) -> isize { self.input() } fn i32(&mut self) -> i32 { self.input() } fn i64(&mut self) -> i64 { self.input() } fn i128(&mut self)-> i128 { self.input() } fn u8(&mut self) -> u8 { self.input() } fn u32(&mut self) -> u32 { self.input() } fn u64(&mut self) -> u64 { self.input() } fn u128(&mut self) -> u128 { self.input() } fn edge(&mut self) -> (usize, usize) { (self.usize1(), self.usize1()) } fn edges(&mut self, m :usize) -> Vec<(usize, usize)> { let mut e = Vec::with_capacity(m); for _ in 0..m { e.push(self.edge()); } e } fn wedge<T:std::str::FromStr>(&mutself) -> (usize, usize, T) { (self.usize1(), self.usize1(), self.input()) } fn wedges<T:std::str::FromStr>(&mut self, m : usize) -> Vec<(usize,usize, T)> { let mut e = Vec::with_capacity(m); for _ in 0..m { e.push(self.wedge()); } e } fn input<T>(&mut self) -> T where T: std::str::FromStr { if self.s.is_empty() { self.reload(); } if let Some(head) = self.s.pop_front() { head.parse::<T>().ok().unwrap() } else { panic!() }} fn tuple<T, U>(&mut self) -> (T, U) where T: std::str::FromStr, U: std::str::FromStr { (self.input(), self.input()) } fn vec<T>(&mut self, n:usize) -> Vec<T> where T: std::str::FromStr { if self.s.is_empty() { self.reload(); } self.s.drain(..n).map(|s| s.parse::<T>().ok().unwrap()).collect::<Vec<T>>() } fn nvec<T>(&mut self) -> Vec<T> where T: std::str::FromStr { let n : usize = self.input(); self.vec(n) } fn chars(&mutself) -> Vec<char> { let s : String = self.input(); s.chars().collect() } fn bytes(&mut self) -> Vec<u8> { let s : String = self.input(); s.bytes().collect() } }// Copyright 2017 Alkis Evlogimenos//// Licensed under the Apache License, Version 2.0 (the "License");// you may not use this file except in compliance with the License.// You may obtain a copy of the License at//// http://www.apache.org/licenses/LICENSE-2.0//// Unless required by applicable law or agreed to in writing, software// distributed under the License is distributed on an "AS IS" BASIS,// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.// See the License for the specific language governing permissions and// limitations under the License.use std::cmp::Ordering::{self, Less, Greater};use std::collections::BTreeMap;/// Extends [`slice`] with fast operations on ordered slices.////// [`slice`]: https://doc.rust-lang.org/stable/std/primitive.slice.htmlpub trait Ext {type Item;/// Returns the index `i` pointing to the first element in the ordered slice/// that is _not less_ than `x`.////// The slice MUST be ordered by the order defined by its elements.////// # Example:////// ```/// # use superslice::*;/// let a = [10, 11, 13, 13, 15];/// assert_eq!(a.lower_bound(&9), 0);/// assert_eq!(a.lower_bound(&10), 0);/// assert_eq!(a.lower_bound(&11), 1);/// assert_eq!(a.lower_bound(&12), 2);/// assert_eq!(a.lower_bound(&13), 2);/// assert_eq!(a.lower_bound(&14), 4);/// assert_eq!(a.lower_bound(&15), 4);/// assert_eq!(a.lower_bound(&16), 5);/// ```fn lower_bound(&self, x: &Self::Item) -> usizewhereSelf::Item: Ord;/// Returns the index `i` pointing to the first element in the ordered slice/// for which `f(self[i]) != Less`.////// The slice MUST be ordered by the order defined by the comparator/// function. The comparator function should take an element and return/// `Ordering` that is consistent with the ordering of the slice.////// # Example:////// ```/// # use superslice::*;/// let b = [1, 2, 3, 6, 9, 9];/// assert_eq!(b.lower_bound(&3), b.lower_bound_by(|x| x.cmp(&3)));/// ```fn lower_bound_by<'a, F>(&'a self, f: F) -> usizewhereF: FnMut(&'a Self::Item) -> Ordering;/// Returns the index `i` pointing to the first element in the ordered slice/// for which `f(self[i]) >= k`.////// The slice MUST be ordered by the order defined by the keys of its/// elements.////// # Example:////// ```/// # use superslice::*;/// let b = [1, 2, 3, 6, 9, 9];/// assert_eq!(b.lower_bound(&3), b.lower_bound_by_key(&6, |x| x * 2));/// ```fn lower_bound_by_key<'a, K, F>(&'a self, k: &K, f: F) -> usizewhereF: FnMut(&'a Self::Item) -> K,K: Ord;/// Returns the index `i` pointing to the first element in the ordered slice/// that is _greater_ than `x`.////// The slice MUST be ordered by the order defined by its elements.////// # Example:////// ```/// # use superslice::*;/// let a = [10, 11, 13, 13, 15];/// assert_eq!(a.upper_bound(&9), 0);/// assert_eq!(a.upper_bound(&10), 1);/// assert_eq!(a.upper_bound(&11), 2);/// assert_eq!(a.upper_bound(&12), 2);/// assert_eq!(a.upper_bound(&13), 4);/// assert_eq!(a.upper_bound(&14), 4);/// assert_eq!(a.upper_bound(&15), 5);/// assert_eq!(a.upper_bound(&16), 5);/// ```fn upper_bound(&self, x: &Self::Item) -> usizewhereSelf::Item: Ord;/// Returns the index `i` pointing to the first element in the ordered slice/// for which `f(self[i]) == Greater`.////// The slice MUST be ordered by the order defined by the comparator/// function. The comparator function should take an element and return/// `Ordering` that is consistent with the ordering of the slice.////// # Example:////// ```/// # use superslice::*;/// let b = [1, 2, 3, 6, 9, 9];/// assert_eq!(b.upper_bound(&3), b.upper_bound_by(|x| x.cmp(&3)));/// ```fn upper_bound_by<'a, F>(&'a self, f: F) -> usizewhereF: FnMut(&'a Self::Item) -> Ordering;/// Returns the index `i` pointing to the first element in the ordered slice/// for which `f(self[i]) > k`.////// The slice MUST be ordered by the order defined by the keys of its/// elements.////// # Example:////// ```/// # use superslice::*;/// let b = [1, 2, 3, 6, 9, 9];/// assert_eq!(b.lower_bound(&3), b.lower_bound_by_key(&6, |x| x * 2));fn upper_bound_by_key<'a, K, F>(&'a self, k: &K, f: F) -> usizewhereF: FnMut(&'a Self::Item) -> K,K: Ord;/// Returns the [`Range`] `a..b` such that all elements in `self[a..b]` are/// _equal_ to `x`.////// The slice MUST be ordered by the order defined by its elements.////// # Example:////// ```/// # use superslice::*;/// let b = [10, 11, 13, 13, 15];/// for i in 9..17 {/// assert_eq!(b.equal_range(&i), (b.lower_bound(&i)..b.upper_bound(&i)));/// }/// ```/// [`Range`]: https://doc.rust-lang.org/stable/std/ops/struct.Range.htmlfn equal_range(&self, x: &Self::Item) -> std::ops::Range<usize>whereSelf::Item: Ord;/// Returns the [`Range`] `a..b` such that for all elements `e` in `self[a..b]`/// `f(e) == Equal`.////// The slice MUST be ordered by the order defined by the comparator/// function. The comparator function should take an element and return/// `Ordering` that is consistent with the ordering of the slice.////// # Example:////// ```/// # use superslice::*;/// let b = [10, 11, 13, 13, 15];/// for i in 9..17 {/// assert_eq!(b.equal_range(&i), b.equal_range_by(|x| x.cmp(&i)));/// }/// ```/// [`Range`]: https://doc.rust-lang.org/stable/std/ops/struct.Range.htmlfn equal_range_by<'a, F>(&'a self, f: F) -> std::ops::Range<usize>whereF: FnMut(&'a Self::Item) -> Ordering;/// Returns the [`Range`] `a..b` such that for all elements `e` in `self[a..b]`/// `f(e) == k`.////// The slice MUST be ordered by the order defined by the keys of its/// elements.////// # Example:////// ```/// # use superslice::*;/// let b = [10, 11, 13, 13, 15];/// for i in 9..17 {/// let i2 = i * 2;/// assert_eq!(b.equal_range(&i), b.equal_range_by_key(&i2, |x| x * 2));/// }/// ```/// [`Range`]: https://doc.rust-lang.org/stable/std/ops/struct.Range.htmlfn equal_range_by_key<'a, K, F>(&'a self, k: &K, f: F) -> std::ops::Range<usize>whereF: FnMut(&'a Self::Item) -> K,K: Ord;/// Transforms the slice into the next permutation from the set of all/// permutations that are lexicographically ordered with respect to the/// natural order of T. Returns true if such permutation exists, otherwise/// transforms the range into the first permutation and returns false.////// # Example:////// ```/// # use superslice::*;/// let mut b = [2, 1, 3];/// let mut v = Vec::new();/// for _ in 0..6 {/// let x = b.next_permutation();/// v.push((x, b.to_vec()));/// }/// assert_eq!(v, &[(true, [2, 3, 1].to_vec()),/// (true, [3, 1, 2].to_vec()),/// (true, [3, 2, 1].to_vec()),/// (false, [1, 2, 3].to_vec()),/// (true, [1, 3, 2].to_vec()),/// (true, [2, 1, 3].to_vec())]);fn next_permutation(&mut self) -> boolwhereSelf::Item: Ord;/// Transforms the slice into the previous permutation from the set of all/// permutations that are lexicographically ordered with respect to the/// natural order of T. Returns true if such permutation exists, otherwise/// transforms the range into the last permutation and returns false.////// # Example:////// ```/// # use superslice::*;/// let mut b = [2, 1, 3];/// let mut v = Vec::new();/// for _ in 0..6 {/// let x = b.prev_permutation();/// v.push((x, b.to_vec()));/// }/// assert_eq!(v, &[(true, [1, 3, 2].to_vec()),/// (true, [1, 2, 3].to_vec()),/// (false, [3, 2, 1].to_vec()),/// (true, [3, 1, 2].to_vec()),/// (true, [2, 3, 1].to_vec()),/// (true, [2, 1, 3].to_vec())]);fn prev_permutation(&mut self) -> boolwhereSelf::Item: Ord;/// Applies `permutation` to the slice. For each element at index `i` the/// following holds:////// new_self[i] == old_self[permutation[i]]////// The transformation happens in O(N) time and O(1) space. `permutation`/// is mutated during the transformation but it is restored to its original/// state on return.////// # Panics////// This function panics if `self` and `permutation` do not have the same/// length or any value in `permutation` is not in `0..self.len()`.////// # Example:////// ```/// # use superslice::*;/// let mut b = ['d', 'a', 'c', 'b'];/// let mut p = [1, 3, 2, 0];/// b.apply_permutation(&mut p);/// assert_eq!(b, ['a', 'b', 'c', 'd']);/// assert_eq!(p, [1, 3, 2, 0]);fn apply_permutation(&mut self, permutation: &mut [isize]);/// Applies the inverse of `permutation` to the slice. For each element at/// index `i` the following holds:////// new_self[permutation[i]] == old_self[i]////// The transformation happens in O(N) time and O(1) space. `permutation`/// is mutated during the transformation but it is restored to its original/// state on return.////// # Panics////// This function panics if `self` and `permutation` do not have the same/// length or any value in `permutation` is not in `0..self.len()`.////// # Example:////// ```/// # use superslice::*;/// let mut b = ['d', 'a', 'c', 'b'];/// let mut p = [3, 0, 2, 1];/// b.apply_inverse_permutation(&mut p);/// assert_eq!(b, ['a', 'b', 'c', 'd']);/// assert_eq!(p, [3, 0, 2, 1]);fn apply_inverse_permutation(&mut self, permutation: &mut [isize]);}impl<T> Ext for [T] {type Item = T;fn lower_bound(&self, x: &Self::Item) -> usizewhereT: Ord,{self.lower_bound_by(|y| y.cmp(x))}fn lower_bound_by<'a, F>(&'a self, mut f: F) -> usizewhereF: FnMut(&'a Self::Item) -> Ordering,{let s = self;let mut size = s.len();if size == 0 {return 0;}let mut base = 0usize;while size > 1 {let half = size / 2;let mid = base + half;let cmp = f(unsafe { s.get_unchecked(mid) });base = if cmp == Less { mid } else { base };size -= half;}let cmp = f(unsafe { s.get_unchecked(base) });base + (cmp == Less) as usize}fn lower_bound_by_key<'a, K, F>(&'a self, k: &K, mut f: F) -> usizewhereF: FnMut(&'a Self::Item) -> K,K: Ord,{self.lower_bound_by(|e| f(e).cmp(k))}fn upper_bound(&self, x: &Self::Item) -> usizewhereT: Ord,{self.upper_bound_by(|y| y.cmp(x))}fn upper_bound_by<'a, F>(&'a self, mut f: F) -> usizewhereF: FnMut(&'a Self::Item) -> Ordering,{let s = self;let mut size = s.len();if size == 0 {return 0;}let mut base = 0usize;while size > 1 {let half = size / 2;let mid = base + half;let cmp = f(unsafe { s.get_unchecked(mid) });base = if cmp == Greater { base } else { mid };size -= half;}let cmp = f(unsafe { s.get_unchecked(base) });base + (cmp != Greater) as usize}fn upper_bound_by_key<'a, K, F>(&'a self, k: &K, mut f: F) -> usizewhereF: FnMut(&'a Self::Item) -> K,K: Ord,{self.upper_bound_by(|e| f(e).cmp(k))}fn equal_range(&self, x: &Self::Item) -> std::ops::Range<usize>whereT: Ord,{self.equal_range_by(|y| y.cmp(x))}fn equal_range_by<'a, F>(&'a self, mut f: F) -> std::ops::Range<usize>whereF: FnMut(&'a Self::Item) -> Ordering,{let s = self;let mut size = s.len();if size == 0 {return 0..0;}let mut base = (0usize, 0usize);while size > 1 {let half = size / 2;let mid = (base.0 + half, base.1 + half);let cmp = (f(unsafe { s.get_unchecked(mid.0) }),f(unsafe { s.get_unchecked(mid.1) }),);base = (if cmp.0 == Less { mid.0 } else { base.0 },if cmp.1 == Greater { base.1 } else { mid.1 },);size -= half;}let cmp = (f(unsafe { s.get_unchecked(base.0) }),f(unsafe { s.get_unchecked(base.1) }),);(base.0 + (cmp.0 == Less) as usize..base.1 + (cmp.1 != Greater) as usize)}fn equal_range_by_key<'a, K, F>(&'a self, k: &K, mut f: F) -> std::ops::Range<usize>whereF: FnMut(&'a Self::Item) -> K,K: Ord,{self.equal_range_by(|e| f(e).cmp(k))}fn next_permutation(&mut self) -> boolwhereSelf::Item: Ord{// Adapted from http://en.cppreference.com/w/cpp/algorithm/next_permutation.if self.len() <= 1 { return false; }let last = self.len() - 1;let mut a = last;loop {let mut b = a;a -= 1;if self[a] < self[b] {b = last;while self[a] >= self[b] {b -= 1;}self.swap(a, b);self[a+1..].reverse();return true;}if a == 0 {self.reverse();return false;}}}fn prev_permutation(&mut self) -> boolwhereSelf::Item: Ord{// Adapted from http://en.cppreference.com/w/cpp/algorithm/prev_permutation.if self.len() <= 1 { return false; }let last = self.len() - 1;let mut a = last;loop {let mut b = a;a -= 1;if self[b] < self[a] {b = last;while self[b] >= self[a] {b -= 1;}self.swap(a, b);self[a+1..].reverse();return true;}if a == 0 {self.reverse();return false;}}}fn apply_permutation(&mut self, perm: &mut [isize]) {assert_eq!(self.len(), perm.len());assert!(self.len() < isize::max_value() as usize);for i in 0..self.len() as isize {let mut c = perm[i as usize];if c < 0 {perm[i as usize] = !c;} else if i != c {loop {let n = perm[c as usize];self.swap(c as usize, n as usize);perm[c as usize] = !n;c = n;if i == c { break; }}}}}fn apply_inverse_permutation(&mut self, perm: &mut [isize]) {assert_eq!(self.len(), perm.len());assert!(self.len() < isize::max_value() as usize);for i in 0..self.len() as isize {let mut c = perm[i as usize];if c < 0 {perm[i as usize] = !c;} else if i != c {loop {self.swap(c as usize, i as usize);let n = perm[c as usize];perm[c as usize] = !n;c = n;if i == c { break; }}}}}}pub trait Ext2 {/// Transforms the slice in the inverse permutation.////// # Panics////// This function panics if any value in `self` is not in `0..self.len()`.////// # Example:////// ```/// # use superslice::*;/// let mut p = [1, 3, 2, 0];/// p.invert_permutation();/// assert_eq!(p, [3, 0, 2, 1]);fn invert_permutation(&mut self);}impl Ext2 for [isize] {fn invert_permutation(&mut self) {assert!(self.len() < isize::max_value() as usize);for i in 0..self.len() as isize {let mut c = self[i as usize];if c < 0 {self[i as usize] = !c;} else if i != c {let mut n = i;loop {let t = self[c as usize];self[c as usize] = !n;n = c;c = t;if c == i {self[i as usize] = n;break;}}}}}}