• API
• FAQ
• Tools
• Trends
• Archive
daily pastebin goal
44%
SHARE
TWEET

# Untitled

a guest Jul 17th, 2017 46 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