template <class T>
struct treap {
private:
struct node {
T key;
unsigned long long priority;
unsigned size;
node *left, *right;
};
struct xorshift {
unsigned long long x,y,z,w;
xorshift(): x(1234567891011121314), y(91734892562378), z(77777777777777), w(986732789462378) {}
unsigned long long next() {
unsigned long long t=x^(x<<11);
x=y;y=z;z=w;
return w=w^(w>>19)^t^(t>>8);
}
};
typedef node *node_ptr;
node_ptr root;
xorshift rng;
unsigned long long next() {
return rng.next();
}
node_ptr new_node(T key) {
node_ptr res=(node_ptr)malloc(sizeof(node));
res->key=key;
res->priority=next();
res->size=1;
res->left=NULL;
res->right=NULL;
return res;
}
unsigned size(node_ptr &root) {
if(root==NULL) return 0;
else return root->size;
}
void update_size(node_ptr &root) {
if(root!=NULL) root->size=1+size(root->left)+size(root->right);
}
node_ptr right_rotation(node_ptr x) {
node_ptr y=x->left,t2=y->right;
x->left=t2;
y->right=x;
update_size(x);
update_size(y);
return y;
}
node_ptr left_rotation(node_ptr y) {
node_ptr x=y->right,t2=x->left;
y->right=t2;
x->left=y;
update_size(y);
update_size(x);
return x;
}
node_ptr insert(node_ptr root, T key) {
if(root==NULL) {
return new_node(key);
}
else if(key<root->key) {
root->left=insert(root->left,key);
if(root->left->priority>root->priority) root=right_rotation(root);
}
else {
root->right=insert(root->right,key);
if(root->right->priority>root->priority) root=left_rotation(root);
}
update_size(root);
return root;
}
node_ptr remove_it(node_ptr root) {
if(root->left==NULL && root->right==NULL) {
return NULL;
}
if(root->left==NULL) {
root=left_rotation(root);
root->left=remove_it(root->left);
update_size(root);
return root;
}
if(root->right==NULL) {
root=right_rotation(root);
root->right=remove_it(root->right);
update_size(root);
return root;
}
if(root->left->priority>root->right->priority) {
root=right_rotation(root);
root->right=remove_it(root->right);
}
else {
root=left_rotation(root);
root->left=remove_it(root->left);
}
update_size(root);
return root;
}
node_ptr erase(node_ptr root, T key) {
if(key<root->key) {
root->left=erase(root->left,key);
}
else if(key>root->key) {
root->right=erase(root->right,key);
}
else {
root=remove_it(root);
}
update_size(root);
return root;
}
unsigned count_less(node_ptr root, T key) {
if(root==NULL) return 0;
else if(key<root->key) return count_less(root->left,key);
else if(key==root->key) return size(root->left);
else return 1+size(root->left)+count_less(root->right,key);
}
T kth(node_ptr root, unsigned k) {
if(1+size(root->left)==k) return root->key;
else if(k<=size(root->left)) return kth(root->left,k);
else return kth(root->right,k-1-size(root->left));
}
bool find(node_ptr root, T key) {
if(root==NULL) return false;
else if(key<root->key) return find(root->left,key);
else if(key>root->key) return find(root->right,key);
else return true;
}
public:
treap(): root(NULL) {}
void clear() {
root=NULL;
rng=xorshift();
}
unsigned size() {
return size(root);
}
bool empty() {
return (size()==0);
}
bool find(T key) {
return find(root,key);
}
void insert(T key) {
if(find(key)==false) root=insert(root,key);
}
void erase(T key) {
if(find(key)==true) root=erase(root,key);
}
T kth(unsigned k) {
return kth(root,k);
}
unsigned count_less(T key) {
return count_less(root,key);
}
};