Treap

class Treap
{
public:
    Treap() : root(0) {}
    ~Treap();

    bool Add(int x, int y);
    bool Delete(int x);
    bool Find(int x);
    int Size();

    struct Node
    {
        int x;
        int y;
        int high;
        Node* left;
        Node* right;

        Node(int x, int y) :x(x), y(y), high(0), left(0), right(0) {}
        ~Node();
        void UpdateSize();
    };

private:
    Node* root;

    Node* find(Node* node, int x);
};

void Treap::Node::UpdateSize()
{
    if (left == 0 && right == 0)
    {
        high = 0;
        return;
    }
    if (left != 0)
        left->UpdateSize();
    if (right != 0)
        right->UpdateSize();
    high = std::max((left != 0) ? left->high : 0, (right != 0) ? right->high :0) + 1;
}

int Treap::Size()
{
    root->UpdateSize();
    return root->high;
}

Treap::Node::~Node()
{
    if (right != 0)
        delete right;
    if (left != 0)
        delete left;
}

Treap::~Treap()
{
    if (root != 0)
        delete root;
}

void split(int x, Treap::Node* M, Treap::Node*& left, Treap::Node*& right)
{
    if (!M)
    {
        left = 0;
        right = 0;
        return;
    }
    else if (M->x >= x)
    {
        split(x, M->left, left, M->left);
        right = M;
    }
    else
    {
        split(x, M->right, M->right, right);
        left = M;

    }
}

Treap::Node* merge(Treap::Node* left, Treap::Node* right)
{
    if (!left)
        return right;
    if (!right)
        return left;
    if (left->y > right->y)
    {
        left->right = merge(left->right, right);
        return left;
    }
    else
    {
        right->left = merge(left, right->left);
        return right;
    }
}

bool Treap::Add(int x, int y)
{
    Treap::Node *left_treap = 0, *right_treap = 0, *new_node = new Treap::Node(x, y);
    split(x, root, left_treap, right_treap);
    root = merge(merge(left_treap, new_node), right_treap);
    return true;
}

Treap::Node* Treap::find(Treap::Node* node, int Key)
{
    if (node == 0)
        return 0;
    if (node->x == Key)
        return node;
    return node->x > Key ? find(node->left, Key) : find(node->right, Key);
}

bool Treap::Find(int x)
{
    return find(root, x);
}

bool Treap::Delete(int x)
{
    Treap::Node *left_treap = 0, *right_treap = 0, *cur_treap = 0;
    split(x - 1, root, left_treap, right_treap);
    split(x, right_treap, cur_treap, right_treap);
    delete cur_treap;
    root = merge(left_treap, right_treap);
    return true;
}