#include<deque>
#include<random>
#include<tuple>
 
std::mt19937 randgen;
 
struct Treap {
    struct Node {
        int key;
        int size;
        unsigned int priority;
        
        Node* left_child;
        Node* right_child;
        
        Node(int new_key) {
            key = new_key;
            size = 1;
            priority = randgen();  // Select a random priority
            left_child = NULL;
            right_child = NULL;
        }
        void update() {  // Update the node data after children have been changed
            size = 1;
            if(left_child) size += left_child->size;
            if(right_child) size += right_child->size;
        }
    };
    
    std::deque<Node> nodes;
    Node* root = NULL;
    
    std::pair<Node*, Node*> split(int key, Node* cur) {
        // Split into two subtrees where left subtree contains nodes with smaller keys while right subtree contains all
        // nodes with greater or equal keys
        if(cur == NULL) {
            return {NULL, NULL};
        }
        
        std::pair<Node*, Node*> result;
        if(key <= cur->key) {
            auto ret = split(key, cur->left_child);
            cur->left_child = ret.second;
            result = {ret.first, cur};
        } else {
            auto ret = split(key, cur->right_child);
            cur->right_child = ret.first;
            result = {cur, ret.second};
        }
        cur->update();
        return result;
    }
    
    Node* merge(Node* left, Node* right) {
        // Merges two subtrees together, assuming that all keys of the left subtree are smaller than all the keys in
        // the right subtree
        if(left == NULL) return right;
        if(right == NULL) return left;
        
        Node* top;
        if(left->priority < right->priority) {
            left->right_child = merge(left->right_child, right);
            top = left;
        } else {
            right->left_child = merge(left, right->left_child);
            top = right;
        }
        top->update();
        return top;
    }
    
    void insert(int key) {
        nodes.push_back(Node(key));
        
        std::pair<Node*, Node*> ret = split(key, root);
        root = merge(merge(ret.first, &nodes.back()), ret.second);
    }
    
    void erase(int key) {
        Node *left, *mid, *right;
        
        std::tie(left, mid) = split(key, root);
        std::tie(mid, right) = split(key+1, mid);
        root = merge(left, right);
    }
};
 
 
int main() {
    Treap treap;
    treap.insert(5);
    treap.erase(5);
}