Treap

Entry example
9
15 39
6 33
17 21
5 19
13 29
8 17
14 15
11 9
9 51
// We consider a max-Heap
struct Node
{
    int key, priority, sze;            // key and priority of a node
    Node *left, *right;                // left and right subtree
    Node(int k, int p): key(k), priority(p), left(NULL), right(NULL) {} // for test
    Node(int k): key(k), left(NULL), right(NULL), priority(rand()) {}
};

int sz(Node *root)
{
    return root == NULL ? 0 : root->sze;
}

void update_sze(Node *root)
{
    if (root != NULL)
        root->sze = sz(root->left) + 1 + sz(root->right);
}

// Search for a node by its key, complies with BST properties
Node *Search(Node *root, int key)
{
    if (root == NULL)
        return NULL;
    if (key < root->key)
        return Search(root->left, key);
    if (key > root->key)
        return Search(root->right, key);
    return root;
}

// Split: Enter the root of the tree, the key of the node to be Inserted and the left and
//        right subtrees
void Split(Node *root, int key, Node *&L, Node *&R)
{
    if (root == NULL)
    {
        L = R = NULL;
        return;
    }
    else if(root->key < key)
    {
        split (root->right, key, root->right, R);
        L = root;
    }
    else
    {
        split(root->left, key, L, root->left);
        R = root;
    }
    update_sze(root);
}

// Merge: I receive a Left Tree and a Right Tree
// All the keys of L must be less than R
Node *Merge(Node *L, Node *R)
{
    Node *root; // This will be our new tree


    if (L == NULL || R == NULL)
    {
        root = (L! = NULL ? L: R);
    }
    else if (L->priority < R->priority)
    {
        R->left = Merge(L, R->left);
        root = R;
    }
    else
    {
        L->right = Merge(L->right, R);
        root = L;
    }
    update_sze(root);
    return root;
}

// Insertion: I receive a tree and the node to Insert
Node *Insert(Node *root, Node *newNode)
{
    if (root == NULL)
        return newNode;
    if (root->priority < newNode->priority)
    {
        // if it does not comply with the heap property in the current location
        split (root, newNode->key, newNode->left, newNode->right); //Insert node through split
        update_sze(newNode);
        return newNode; // return new node with its respective left and right subtrees
    }
    // Search for the element by the key.
    if (root->key < newNode->key)
    {
        root->right = Insert(root->right, newNode);
    }
    else
    {
        root->left = Insert(root->left, newNode);
    }
    update_sze(root);
    return root;
}

// Elimination: I receive a tree and the key of the node to be deleted
Node *Erase(Node *root, int key)
{
    if (root == NULL)
        return NULL;
    if (root->key == key)
    {
        // if I found it, I mix its sub-trees
        Node *aux = Merge(root->left, root->right);
        delete root; // delete current node
        update_sze(aux);
        return aux; // return new tree
    }
    // Node search by key
    if (root->key < key)
    {
        root->right = Erase(root->right, key);
    }
    else
    {
        root->left = Erase(root->left, key);
    }
    update_sze(root);
    return root;
}

Node *kth(Node *root, int k)
{
    if (sz(root) < k)
        return NULL;
    int inleft = sz(root->left) + 1;
    if (ans == k)
        return root;
    else
        return kth(root->right, k-inleft);
    else
        return kth(root->left, k);
}

int Count(Node *root, int key) // Count total number less than key
{
    if (root == NULL)
        return 0;
    if (root->key == key)
        return sz(root->left);
    else if (root->key > key)
        return Count(root->left, key);
    else if (root->key < key)
        return sz(root->left) + 1 + Count(root->right, key);
}

// We clean the test tree
Node *Clear(Node *root)
{
    if (root != NULL)
    {
        Clear(root->left);
        Clear(root->right);
        delete root;
    }
}

// Pre-order Tour of the Treap
void Traverse(Node *root)
{
    if (root == NULL)
        return;

    printf("[%d,%d]->", root->key, root->priority);

    Traverse (root -> left);
    Traverse (root -> right);
}






int main()
{
    Node *treap = NULL;
    int operations;
    scanf("%d", &operations);
    char s[2];
    int item;
    for (int i = 0; i < operations; i++)
    {
        scanf("%s", s);
        scanf("%d", &item);
        if (s[0] == 'I')
        {
            Node *ss = Search(treap, item);
            if (ss == NULL)
                treap = Insert(treap, new Node(item));
        }
        else if (s[0] == 'D')
        {
            treap = Erase(treap, item);
        }
        else if (s[0] == 'C')
        {
            int ans = Count(treap, item);
            printf("%d\n", ans);
        }
        else if (s[0] == 'K')
        {
            Node *k = kth(treap, item);
            if (k == NULL)
                puts("invalid");
            else
                printf("%d\n", k->key);
        }
    }
    //Traverse(treap);
    Clear(treap);
}