fork(2) download
copy 
  1. /// Treap (balanced binary search tree)
  2. /// Reference: https://w...content-available-to-author-only...e.net/iwiwi/2-12188757
  3. /// Verified by: ARC061-D (http://a...content-available-to-author-only...r.jp/submissions/1172709)
  4. /// 2150ms for n = 9*10^5, maybe a bit slow for an O(n * log(n))-time algorithm...
  5. #[derive(Clone, Debug)]
  6. enum Treap<T> {
  7.     Bin(
  8.         usize, // size
  9.         i64, // priority
  10.         T, // value
  11.         Box<Treap<T>>, // left
  12.         Box<Treap<T>>, // right
  13.     ),
  14.     Tip,
  15. }
  16.  
  17. impl<T: Ord> Treap<T> {
  18.     pub fn new() -> Self { Treap::Tip }
  19.     pub fn singleton(v: T, pri: i64) -> Self {
  20.         use Treap::*;
  21.         Bin(1, pri, v, Box::new(Tip), Box::new(Tip))
  22.     }
  23.     pub fn size(&self) -> usize {
  24.         use Treap::*;
  25.         match *self {
  26.             Tip => 0,
  27.             Bin(t, _,  _, _, _) => t,
  28.         }
  29.     }
  30.     // Merges two BST. Their ownership is taken.
  31.     pub fn merge(left: Self, right: Self) -> Self {
  32.         use Treap::*;
  33.         match (left, right) {
  34.             (Tip, Tip) => Tip,
  35.             (Tip, x) => x,
  36.             (x, Tip) => x,
  37.             (Bin(lsize, lpri, lelem, lleft, lright),
  38.              Bin(rsize, rpri, relem, rleft, rright)) => {
  39.                 if lpri > rpri {
  40.                     let right = Bin(rsize, rpri, relem, rleft, rright);
  41.                     let mut ret = Bin(lsize, lpri, lelem, lleft,
  42.                                   Box::new(Self::merge(*lright, right)));
  43.                     ret.update();
  44.                     ret
  45.                 } else {
  46.                     let left = Bin(lsize, lpri, lelem, lleft, lright);
  47.                     let mut ret = Bin(rsize, rpri, relem,
  48.                                       Box::new(Self::merge(left, *rleft)),
  49.                                       rright);
  50.                     ret.update();
  51.                     ret
  52.                 }
  53.             }
  54.         }
  55.     }
  56.     pub fn split(self, k: usize) -> (Self, Self) {
  57.         use Treap::*;
  58.         match self {
  59.             Tip => (Tip, Tip),
  60.             Bin(size, pri, elem, left, right) => {
  61.                 if k <= left.size() {
  62.                     let (sl, sr) = Self::split(*left, k);
  63.                     let mut ret = Bin(size, pri, elem, Box::new(sr), right);
  64.                     ret.update();
  65.                     (sl, ret)
  66.                 } else {
  67.                     let (sl, sr) = Self::split(*right, k - left.size() - 1);
  68.                     let mut ret = Bin(size, pri, elem, left, Box::new(sl));
  69.                     ret.update();
  70.                     (ret, sr)
  71.                 }
  72.             }
  73.         }
  74.     }
  75.     fn update(&mut self) {
  76.         use Treap::*;
  77.         match *self {
  78.             Tip => (),
  79.             Bin(ref mut lsize, ref _pri, ref _elem, ref left, ref right) => {
  80.                 *lsize = left.size() + right.size() + 1;
  81.             },
  82.         }
  83.     }
  84.     fn insert_at(self, v: T, pri: i64, k: usize) -> Self {
  85.         use Treap::*;
  86.         // Speed up: compare the priority
  87.         match self {
  88.             Tip => Self::singleton(v, pri),
  89.             Bin(size, spri, elem, left, right) => {
  90.                 let lsize = left.size();
  91.                 if spri <= pri {
  92.                     let cself = Bin(size, spri, elem, left, right);
  93.                     let (left, right) = cself.split(k);
  94.                     return Bin(size + 1, pri, v,
  95.                                Box::new(left), Box::new(right));
  96.                 }
  97.                 if k < lsize {
  98.                     return Bin(size + 1, spri, elem,
  99.                                Box::new((*left).insert_at(v, pri, k)),
  100.                                right);
  101.                 }
  102.                 if k >= lsize + 1 {
  103.                     return Bin(size + 1, spri, elem,
  104.                                left,
  105.                                Box::new((*right)
  106.                                         .insert_at(v, pri, k - lsize - 1)));
  107.                 }
  108.                 let cself = Bin(size, spri, elem, left, right);
  109.                 let sing = Self::singleton(v, pri);
  110.                 let (left, right) = cself.split(k);
  111.                 let tmp = Self::merge(left, sing);
  112.                 Self::merge(tmp, right)
  113.             }
  114.         }
  115.     }
  116.     fn erase_at(self, k: usize) -> Self {
  117.         use Treap::*;
  118.         match self {
  119.             Tip => Tip,
  120.             Bin(size, pri, elem, left, right) => {
  121.                 if k < left.size() {
  122.                     return Bin(size - 1, pri, elem,
  123.                                Box::new((*left).erase_at(k)), right);
  124.                 }
  125.                 if k == left.size() {
  126.                     return Self::merge(*left, *right); // hit
  127.                 }
  128.                 let lsize = left.size();
  129.                 return Bin(size - 1, pri, elem,
  130.                            left,
  131.                            Box::new((*right).erase_at(k - lsize - 1)));
  132.             }
  133.         }
  134.     }
  135.     fn find_index(&self, t: &T) -> (usize, bool) {
  136.         use Treap::*;
  137.         use std::cmp::Ordering;
  138.         let mut offset = 0;
  139.         let mut tap = self;
  140.         loop {
  141.             match *tap {
  142.                 Tip => return (offset, false),
  143.                 Bin(_, _, ref elem, ref left, ref right) => {
  144.                     match elem.cmp(t) {
  145.                         Ordering::Equal => return (offset + left.size(), true),
  146.                         Ordering::Greater =>
  147.                             tap = left,
  148.                         Ordering::Less => {
  149.                             offset += left.size() + 1;
  150.                             tap = right;
  151.                         },
  152.                     }
  153.                 }
  154.             }
  155.         }
  156.     }
  157.     #[allow(dead_code)]
  158.     fn insert(self, v: T, pri: i64) -> Self {
  159.         let (idx, found) = self.find_index(&v);
  160.         if found {
  161.             self
  162.         } else {
  163.             self.insert_at(v, pri, idx)
  164.         }
  165.     }
  166.     #[allow(dead_code)]
  167.     fn erase(self, v: &T) -> Self {
  168.         let (idx, found) = self.find_index(v);
  169.         if found {
  170.             self.erase_at(idx)
  171.         } else {
  172.             self
  173.         }
  174.     }
  175.     fn into_vec_sub(self, vec: &mut Vec<T>) {
  176.         use Treap::*;
  177.         match self {
  178.             Tip => (),
  179.             Bin(_, _, elem, left, right) => {
  180.                 left.into_vec_sub(vec);
  181.                 vec.push(elem);
  182.                 right.into_vec_sub(vec);
  183.             }
  184.         }
  185.     }
  186.     #[allow(dead_code)]
  187.     pub fn into_vec(self) -> Vec<T> {
  188.         let mut ret = Vec::new();
  189.         self.into_vec_sub(&mut ret);
  190.         ret
  191.     }
  192. }
  193.  
  194. fn depth<T>(t: &Treap<T>) -> usize {
  195.     match *t {
  196.         Treap::Tip => 0,
  197.         Treap::Bin(_, _, _, ref left, ref right) => {
  198.             std::cmp::max(depth(left), depth(right)) + 1
  199.         }
  200.     }
  201. }
  202.  
  203. fn main() {
  204.     let mut bst = Treap::Tip::<usize>;
  205.     let mut seed: i64 = 0xdeadc0de;
  206.     let mut next = || {
  207.         seed = seed.wrapping_mul(0x12345678deadc0d1).wrapping_add(0x1551);
  208.         seed
  209.     };
  210.     const N: usize = 30000;
  211.     for _ in 0 .. 1000 { next(); }
  212.     let mut cur_depth = 0;
  213.     for i in 0 .. N {
  214.         let elem = (next() & 0xffff_ffff) as usize;
  215.         bst = bst.insert(elem, next());
  216.         let dep = depth(&bst);
  217.         if cur_depth != dep {
  218.             println!("i = {}, depth = {}", i, dep);
  219.             cur_depth = dep;
  220.         }
  221.     }
  222. }
  223.  
Success #stdin #stdout 14.96s 16936KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
i = 0, depth = 1
i = 1, depth = 2
i = 3, depth = 3
i = 4, depth = 4
i = 10, depth = 5
i = 13, depth = 6
i = 15, depth = 7
i = 21, depth = 8
i = 28, depth = 9
i = 30, depth = 10
i = 34, depth = 11
i = 35, depth = 12
i = 44, depth = 10
i = 57, depth = 11
i = 85, depth = 12
i = 97, depth = 13
i = 106, depth = 12
i = 108, depth = 13
i = 109, depth = 12
i = 118, depth = 13
i = 162, depth = 14
i = 175, depth = 15
i = 187, depth = 16
i = 200, depth = 17
i = 210, depth = 18
i = 234, depth = 16
i = 241, depth = 15
i = 266, depth = 16
i = 270, depth = 17
i = 275, depth = 18
i = 321, depth = 17
i = 342, depth = 15
i = 388, depth = 16
i = 389, depth = 15
i = 408, depth = 16
i = 496, depth = 17
i = 505, depth = 18
i = 547, depth = 17
i = 572, depth = 18
i = 769, depth = 19
i = 780, depth = 18
i = 795, depth = 19
i = 826, depth = 20
i = 915, depth = 21
i = 1083, depth = 22
i = 1164, depth = 20
i = 1370, depth = 21
i = 1380, depth = 20
i = 1469, depth = 21
i = 1651, depth = 22
i = 1675, depth = 23
i = 1680, depth = 24
i = 1701, depth = 25
i = 1748, depth = 26
i = 2014, depth = 27
i = 2188, depth = 25
i = 2303, depth = 26
i = 2514, depth = 27
i = 2521, depth = 28
i = 2696, depth = 29
i = 2717, depth = 30
i = 3150, depth = 31
i = 3205, depth = 30
i = 3211, depth = 31
i = 3369, depth = 28
i = 3499, depth = 29
i = 3559, depth = 28
i = 3995, depth = 25
i = 4171, depth = 26
i = 4172, depth = 24
i = 4246, depth = 25
i = 4360, depth = 26
i = 4705, depth = 27
i = 5035, depth = 28
i = 5268, depth = 29
i = 6424, depth = 30
i = 7789, depth = 29
i = 8015, depth = 30
i = 8437, depth = 29
i = 8601, depth = 30
i = 8770, depth = 31
i = 8834, depth = 32
i = 9455, depth = 31
i = 9784, depth = 32
i = 10760, depth = 30
i = 11359, depth = 31
i = 12052, depth = 30
i = 12390, depth = 31
i = 12448, depth = 32
i = 12599, depth = 33
i = 12671, depth = 34
i = 13032, depth = 32
i = 13442, depth = 33
i = 13968, depth = 34
i = 13972, depth = 33
i = 14664, depth = 32
i = 15098, depth = 33
i = 16353, depth = 32
i = 16618, depth = 33
i = 17272, depth = 34
i = 17452, depth = 35
i = 18572, depth = 33
i = 18842, depth = 34
i = 19099, depth = 33
i = 20659, depth = 34
i = 20880, depth = 33
i = 21961, depth = 34
i = 22591, depth = 35
i = 23721, depth = 36
i = 24558, depth = 37
i = 24985, depth = 35
i = 25119, depth = 34
i = 26672, depth = 35
i = 26850, depth = 34
i = 27000, depth = 33
i = 27218, depth = 34
i = 27391, depth = 33
i = 28182, depth = 32
i = 29011, depth = 33
i = 29537, depth = 34
https://ideone.com/pW7sBf
Treap in Rust<br>Inserting 10^4 elements in a random order
language:
Rust (rust 1.56)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!