SHARE
TWEET

Untitled

a guest Jul 17th, 2017 44 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <cstdio>
  2. #include <algorithm>
  3.  
  4. using namespace std;
  5.  
  6. #define dummy NULL
  7.  
  8. struct node{
  9.  node *l, *r;
  10.  int v, p, s;
  11.  node( int _v = 0 ) { l = r = dummy; v = _v; p = rand(); s = 1; }
  12. };
  13.  
  14.  
  15. struct Treap{
  16.  node *root;
  17.  Treap( ) { root = dummy; }
  18.  
  19.  inline int getp( node *x ) { if( x == dummy ) return 0; else return x->p; }
  20.  inline int gets( node *x ) { if( x == dummy ) return 0; else return x->s; }
  21.  inline void rebuild( node *&x ) { if( x != dummy ) x->s = gets( x->l )+gets( x->r )+1; }
  22.  
  23.  inline void rot_r( node *&x ) { node *y = x->l; x->l = y->r; y->r = x; rebuild( x->r ); rebuild( x ); x = y; }
  24.  inline void rot_l( node *&x ) { node *y = x->r; x->r = y->l; y->l = x; rebuild( x->l ); rebuild( x ); x = y; }
  25.  
  26.  void insert( node *&x, int v ) {
  27.   if( x == dummy ) { x = new node( v ); return; }
  28.  
  29.   if( x->v > v ) insert( x->l, v );
  30.   else insert( x->r, v );
  31.  
  32.   if( getp( x->l ) > x->p ) rot_r( x );
  33.   else if( getp( x->r ) > x->p ) rot_l( x );
  34.  
  35.   rebuild( x );
  36.  }
  37.  
  38.  void erase( node *&x, int v ) {
  39.   if( gets( x ) == 1 ) { delete x; return; }
  40.   if( x->v == v ) {
  41.     if( getp( x->l ) > getp( x->r ) ) rot_r( x );
  42.     else rot_l( x );
  43.     erase( x, v ); return;
  44.   }
  45.  
  46.   if( x->v > v ) erase( x->l, v );
  47.   else erase( x->r, v );
  48.  
  49.   rebuild( x );
  50.  }
  51.  
  52.  int kth( node *&x, int k ) {
  53.   if( x == dummy ) return -1;
  54.   if( gets( x->l )+1 == k ) return x->v;
  55.   if( gets( x->l ) >= k ) return kth( x->l, k );
  56.   else return kth( x->r, k-gets( x->l )-1 );
  57.  }
  58.  
  59. }T;
  60.  
  61. int main( void ) {
  62.  for( int i = 0; i < 100000; ++i )
  63.     T.insert( T.root, i );
  64.  
  65.  
  66.  for( int i = 3; i < 100000; ++i ) {
  67.     T.erase( T.root, i );
  68.     printf( "%d %d\n", T.root->v, T.root->s );
  69.  }
  70.  
  71.  return 0;
  72. }
RAW Paste Data
Top