fork download
  1. template <class T>
  2. struct treap {
  3. private:
  4. struct node {
  5. T key;
  6. unsigned long long priority;
  7. unsigned size;
  8. node *left, *right;
  9. };
  10. struct xorshift {
  11. unsigned long long x,y,z,w;
  12. xorshift(): x(1234567891011121314), y(91734892562378), z(77777777777777), w(986732789462378) {}
  13. unsigned long long next() {
  14. unsigned long long t=x^(x<<11);
  15. x=y;y=z;z=w;
  16. return w=w^(w>>19)^t^(t>>8);
  17. }
  18. };
  19. typedef node *node_ptr;
  20. node_ptr root;
  21. xorshift rng;
  22. unsigned long long next() {
  23. return rng.next();
  24. }
  25. node_ptr new_node(T key) {
  26. node_ptr res=(node_ptr)malloc(sizeof(node));
  27. res->key=key;
  28. res->priority=next();
  29. res->size=1;
  30. res->left=NULL;
  31. res->right=NULL;
  32. return res;
  33. }
  34. unsigned size(node_ptr &root) {
  35. if(root==NULL) return 0;
  36. else return root->size;
  37. }
  38. void update_size(node_ptr &root) {
  39. if(root!=NULL) root->size=1+size(root->left)+size(root->right);
  40. }
  41. node_ptr right_rotation(node_ptr x) {
  42. node_ptr y=x->left,t2=y->right;
  43. x->left=t2;
  44. y->right=x;
  45. update_size(x);
  46. update_size(y);
  47. return y;
  48. }
  49. node_ptr left_rotation(node_ptr y) {
  50. node_ptr x=y->right,t2=x->left;
  51. y->right=t2;
  52. x->left=y;
  53. update_size(y);
  54. update_size(x);
  55. return x;
  56. }
  57. node_ptr insert(node_ptr root, T key) {
  58. if(root==NULL) {
  59. return new_node(key);
  60. }
  61. else if(key<root->key) {
  62. root->left=insert(root->left,key);
  63. if(root->left->priority>root->priority) root=right_rotation(root);
  64. }
  65. else {
  66. root->right=insert(root->right,key);
  67. if(root->right->priority>root->priority) root=left_rotation(root);
  68. }
  69. update_size(root);
  70. return root;
  71. }
  72. node_ptr remove_it(node_ptr root) {
  73. if(root->left==NULL && root->right==NULL) {
  74. return NULL;
  75. }
  76. if(root->left==NULL) {
  77. root=left_rotation(root);
  78. root->left=remove_it(root->left);
  79. update_size(root);
  80. return root;
  81. }
  82. if(root->right==NULL) {
  83. root=right_rotation(root);
  84. root->right=remove_it(root->right);
  85. update_size(root);
  86. return root;
  87. }
  88. if(root->left->priority>root->right->priority) {
  89. root=right_rotation(root);
  90. root->right=remove_it(root->right);
  91. }
  92. else {
  93. root=left_rotation(root);
  94. root->left=remove_it(root->left);
  95. }
  96. update_size(root);
  97. return root;
  98. }
  99. node_ptr erase(node_ptr root, T key) {
  100. if(key<root->key) {
  101. root->left=erase(root->left,key);
  102. }
  103. else if(key>root->key) {
  104. root->right=erase(root->right,key);
  105. }
  106. else {
  107. root=remove_it(root);
  108. }
  109. update_size(root);
  110. return root;
  111. }
  112. unsigned count_less(node_ptr root, T key) {
  113. if(root==NULL) return 0;
  114. else if(key<root->key) return count_less(root->left,key);
  115. else if(key==root->key) return size(root->left);
  116. else return 1+size(root->left)+count_less(root->right,key);
  117. }
  118. T kth(node_ptr root, unsigned k) {
  119. if(1+size(root->left)==k) return root->key;
  120. else if(k<=size(root->left)) return kth(root->left,k);
  121. else return kth(root->right,k-1-size(root->left));
  122. }
  123. bool find(node_ptr root, T key) {
  124. if(root==NULL) return false;
  125. else if(key<root->key) return find(root->left,key);
  126. else if(key>root->key) return find(root->right,key);
  127. else return true;
  128. }
  129. public:
  130. treap(): root(NULL) {}
  131. void clear() {
  132. root=NULL;
  133. rng=xorshift();
  134. }
  135. unsigned size() {
  136. return size(root);
  137. }
  138. bool empty() {
  139. return (size()==0);
  140. }
  141. bool find(T key) {
  142. return find(root,key);
  143. }
  144. void insert(T key) {
  145. if(find(key)==false) root=insert(root,key);
  146. }
  147. void erase(T key) {
  148. if(find(key)==true) root=erase(root,key);
  149. }
  150. T kth(unsigned k) {
  151. return kth(root,k);
  152. }
  153. unsigned count_less(T key) {
  154. return count_less(root,key);
  155. }
  156. };
  157.  
Compilation error #stdin compilation error #stdout 0s 0KB
stdin
Standard input is empty
compilation info
prog.cpp: In member function 'treap<T>::node* treap<T>::new_node(T)':
prog.cpp:26:45: error: there are no arguments to 'malloc' that depend on a template parameter, so a declaration of 'malloc' must be available [-fpermissive]
   node_ptr res=(node_ptr)malloc(sizeof(node));
                                             ^
prog.cpp:26:45: note: (if you use '-fpermissive', G++ will accept your code, but allowing the use of an undeclared name is deprecated)
prog.cpp:30:13: error: 'NULL' was not declared in this scope
   res->left=NULL;
             ^
prog.cpp: In member function 'unsigned int treap<T>::size(treap<T>::node*&)':
prog.cpp:35:12: error: 'NULL' was not declared in this scope
   if(root==NULL) return 0;
            ^
prog.cpp: In member function 'void treap<T>::update_size(treap<T>::node*&)':
prog.cpp:39:12: error: 'NULL' was not declared in this scope
   if(root!=NULL) root->size=1+size(root->left)+size(root->right);
            ^
prog.cpp: In member function 'treap<T>::node* treap<T>::insert(treap<T>::node_ptr, T)':
prog.cpp:58:12: error: 'NULL' was not declared in this scope
   if(root==NULL) {
            ^
prog.cpp: In member function 'treap<T>::node* treap<T>::remove_it(treap<T>::node_ptr)':
prog.cpp:73:18: error: 'NULL' was not declared in this scope
   if(root->left==NULL && root->right==NULL) {
                  ^
prog.cpp:76:18: error: 'NULL' was not declared in this scope
   if(root->left==NULL) {
                  ^
prog.cpp:82:19: error: 'NULL' was not declared in this scope
   if(root->right==NULL) {
                   ^
prog.cpp: In member function 'unsigned int treap<T>::count_less(treap<T>::node_ptr, T)':
prog.cpp:113:12: error: 'NULL' was not declared in this scope
   if(root==NULL) return 0;
            ^
prog.cpp: In member function 'bool treap<T>::find(treap<T>::node_ptr, T)':
prog.cpp:124:12: error: 'NULL' was not declared in this scope
   if(root==NULL) return false;
            ^
prog.cpp: In constructor 'treap<T>::treap()':
prog.cpp:130:16: error: 'NULL' was not declared in this scope
  treap(): root(NULL) {}
                ^
prog.cpp: In member function 'void treap<T>::clear()':
prog.cpp:132:8: error: 'NULL' was not declared in this scope
   root=NULL;
        ^
stdout
Standard output is empty