#include <array>
#include <bits/stdc++.h>
#include <initializer_list>
#include <random>

using X = int;
using Y = int;

int genRandInt(int from, int to);

enum class Child
{
    left = 0,
    right = 1
};

struct Node
{
    X x;
    Y y;
    size_t index;
    Node* children[2];

    const Node* operator[](Child child) const noexcept;
    Node*& operator[](Child child) noexcept;
};

using NodeAndXComparator = bool(*)(const Node&, X);

bool is_x_left_subtree(const Node& node, X x);
bool is_x_right_subtree(const Node& node, X x);
constexpr auto children_and_x_comparator();

void print(const Node* node, size_t offset);
const Node* find(const Node* node, X x);
const Node& descend(const Node& node, Child child);
std::pair<Node*, Node*> split(Node* node, X x);
Node* merge(Node* left, Node* right);

class Treap final
{
public:
    explicit Treap();

    void insert(X x);
    void erase(X x);
    bool contains(X x) const;

    std::pair<Treap, Treap> split(X x) &&;
    void merge(Treap&& other);

    X getMinX() const;
    X getMaxX() const;

    void print() const;

private:
    explicit Treap(Node* _root);
    Node* root;
};

int genRandInt(const int from, const int to)
{
    static std::mt19937_64 gen;

    std::uniform_int_distribution distribution(from, to);

    return distribution(gen);
}

bool is_x_left_subtree(const Node& node, const X x)
{
    return x < node.x;
}

bool is_x_right_subtree(const Node& node, const X x)
{
    return x > node.x;
}

constexpr auto children_and_x_comparator()
{
    return std::array
    {
        std::pair<Child, NodeAndXComparator>{Child::left, is_x_left_subtree},
        std::pair<Child, NodeAndXComparator>{Child::right, is_x_right_subtree}
    };
}

Node*& Node::operator[](const Child child) noexcept
{
    return children[static_cast<int>(child)];
}

const Node* Node::operator[](const Child child) const noexcept
{
    return children[static_cast<int>(child)];
}

const Node* find(const Node* node, const X x)
{
    if (nullptr == node)
    {
        return node;
    }

    if (node->x == x)
    {
        return node;
    }

    for (const auto& [child, comparator] : children_and_x_comparator())
    {
        if (comparator(*node, x))
        {
            return find((*node)[child], x);
        }
    }

    return nullptr;
}

constexpr Child other(const Child child)
{
    return static_cast<Child>(1 - static_cast<int>(child));
}

Node* merge(Node* nodes[2])
{
    for (const Child child : {Child::left, Child::right})
    {
        if (nodes[static_cast<int>(child)] == nullptr)
            return nodes[static_cast<int>(other(child))];
    }

    for (const Child child : {Child::left, Child::right})
    {
        if (nodes[static_cast<int>(child)]->y > nodes[static_cast<int>(other(child))]->y)
        {
            Node* root = nodes[static_cast<int>(child)];

            nodes[static_cast<int>(child)] = (*root)[other(child)];

            (*root)[other(child)] = merge(nodes);

            return root;
        }
    }

    assert(false && "Unreachable");
}

Node* merge(Node* const left, Node* const right)
{
    if (nullptr == left) return right;
    if (nullptr == right) return left;

    Node* root = nullptr;
    if (left->y > right->y)
    {
        root = left;
        (*left)[Child::right] = merge((*left)[Child::right], right);
    }
    else
    {
        root = right;
        (*right)[Child::left] = merge(left, (*right)[Child::left]);
    }

    return root;
}

std::pair<Node*, Node*> split(Node* node, X x)
{
    if (nullptr == node) return {nullptr, nullptr};

    if (is_x_left_subtree(*node, x))
    {
        auto [left, right] = split((*node)[Child::left], x);
        (*node)[Child::left] = right;

        return {left, node};
    }
    else
    {
        auto [left, right] = split((*node)[Child::right], x);
        (*node)[Child::right] = left;

        return {node, right};
    }
}

const Node& descend(const Node& node, const Child child)
{
    if (nullptr != node[child])
    {
        return descend(*node[child], child);
    }
    else
    {
        return node;
    }
}

void print(const Node* const node, size_t offset)
{
    if (nullptr == node)
    {
        return;
    }

    print((*node)[Child::left], offset + 1);
    for (size_t i = 0; i < offset; ++i)
    {
        std::cout << "  ";
    }
    std::cout << "x: " << node->x << "; y: " << node->y << "; index: " << node->index << std::endl;
    print((*node)[Child::right], offset + 1);
}

Treap::Treap()
    : root{nullptr}
{
}

Treap::Treap(Node* _root)
    : root{_root}
{
}

void Treap::print() const
{
    std::cout << "Treap" << std::endl;

    ::print(root, 0);

    std::cout << std::endl;
}

bool Treap::contains(X x) const
{
    return nullptr != find(root, x);
}

X Treap::getMinX() const
{
    assert(nullptr != root);
    return descend(*root, Child::left).x;
}

X Treap::getMaxX() const
{
    assert(nullptr != root);
    return descend(*root, Child::right).x;
}

void Treap::insert(const X x)
{
    constexpr int max_y = 100;
    assert(not contains(x));

    auto [left, right] = std::move(*this).split(x);

    root = new Node
    {
          x
        , genRandInt(0, max_y)
        , 0
        , {nullptr, nullptr}
    };

    left.merge(std::move(*this));
    left.merge(std::move(right));

    root = left.root;
    left.root = nullptr;
}

std::pair<Treap, Treap> Treap::split(X x) &&
{
    const auto& [rootLeft, rootRight] = ::split(root, x);
    root = nullptr;

    return {Treap(rootLeft), Treap(rootRight)};
}

void Treap::merge(Treap&& t)
{
    assert(root == nullptr || t.root == nullptr || getMaxX() < t.getMinX());

    root = ::merge(root, t.root);
    t.root = nullptr;
}

int main(const int argc, const char** argv)
{
    Treap t;

    for (int i = 0; i < 10; ++i)
    {
        X x = genRandInt(0, 100);
        if (not t.contains(x))
        {
            t.insert(x);
        }
    }

    t.print();

    auto [left, right] = std::move(t).split(50);

    left.print();
    right.print();
}