fork 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.         bst = bst.insert(i, next());
  215.         let dep = depth(&bst);
  216.         if cur_depth != dep {
  217.             println!("i = {}, depth = {}", i, dep);
  218.             cur_depth = dep;
  219.         }
  220.     }
  221. }
  222.  
Success #stdin #stdout 11.7s 16936KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
i = 0, depth = 1
i = 1, depth = 2
i = 2, depth = 3
i = 4, depth = 4
i = 5, depth = 5
i = 7, depth = 6
i = 16, depth = 7
i = 27, depth = 8
i = 42, depth = 9
i = 74, depth = 10
i = 82, depth = 11
i = 133, depth = 12
i = 136, depth = 13
i = 137, depth = 14
i = 162, depth = 15
i = 213, depth = 16
i = 219, depth = 17
i = 237, depth = 18
i = 295, depth = 19
i = 395, depth = 20
i = 421, depth = 21
i = 429, depth = 22
i = 882, depth = 23
i = 1352, depth = 24
i = 1834, depth = 25
i = 1957, depth = 26
i = 2167, depth = 27
i = 8104, depth = 28
i = 8345, depth = 29
i = 11634, depth = 30
i = 11786, depth = 31
i = 16875, depth = 32
i = 17541, depth = 33
i = 17669, depth = 34
i = 26158, depth = 35
https://ideone.com/tSrw7u
Treap in Rust<br>Inserting 10^4 elements in ascending order
language:
Rust (rust 1.56)
created:
6 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!