#pragma once
#include <random>
#include <iostream>
using namespace std;

mt19937 gen(time(0));

struct Node {
    int x, y;

    Node *left, *right;

    Node(int x) : x(x), y(gen()), left(nullptr), right(nullptr) {}

    ~Node() {
        // Это деструктор, он вызывается, когда удаляется
        // объект типа Node.
        if (left) {
            // Чтобы освободить память под указателем,
            // нужно вызывать delete.
            delete left;
        }
        if (right) {
            delete right;
        }  
    }
};

pair<Node*, Node*> split(Node* t, int x) {
    // Делим элементы t на два дерева так, чтобы в первом дереве были
    // элементы со значениями <= x, а во втором --- со значениями > x.
    if (t == nullptr) {
        return { nullptr, nullptr };
    }
    if (t->x <= x) {
        auto split_right = split(t->right, x);
        t->right = split_right.first;
        return { t, split_right.second };
    }
    else {
        auto split_left = split(t->left, x);
        t->left = split_left.second;
        return { split_left.first, t };
    }
}


Node* merge(Node* l, Node* r) {
    // Объединяем деревья l и r в одно дерево так,
    // чтобы в нем все элементы l были расположены
    // левее элементов r.
    if (l == nullptr) {
        return r;
    }
    if (r == nullptr) {
        return l;
    }
    if (l->y > r->y) {
        l->right = merge(l->right, r);
        return l;
    }
    else {
        r->left = merge(l, r->left);
        return r;
    }
}

Node* insert(Node* t, int x) {
    auto split_tree = split(t, x);
    // new Node(x); — Новая вершина со значением x.
    // 
    // Node(x) — Возвращает новый объект типа Node.
    // new Node(x) — Создает новый объект типа Node, возвращает указатель на него.
    Node* right = merge(new Node(x), split_tree.second);
    return merge(split_tree.first, right);
}

Node* remove(Node* t, int x) {
    // Удаляет из t все элементы, равные x.
    auto split_tree = split(t, x);
    auto split_left = split(split_tree.first, x - 1);
    // t:
    // 1) split_left.first  (<= x - 1)
    // 2) split_left.second (== x)
    // 3) split_tree.second (> x)
    // 
    // Удаляем дерево с элементами, равными x:
    delete split_left.second;
    return merge(split_left.first, split_tree.second);
}

bool find(Node* t, int x) {
    if (t == nullptr) {
        return false;
    }
    if (t->x == x) {
        return true;
    }
    if (t->x > x) {
        return find(t->left, x);
    }
    else {
        return find(t->right, x);
    }
}





void print_treap_recursive(Node* t) {
    if (t == nullptr) {
        return;
    }
    cout << "(";
    print_treap_recursive(t->left);
    cout << t->x;
    print_treap_recursive(t->right);
    cout << ")";
}

void print_treap_recursive_with_depth(Node* t, int depth) {
    if (t == nullptr) {
        return;
    }
    print_treap_recursive_with_depth(t->left, depth + 1);
    for (int i = 0; i < depth; ++i) {
        cout << ".";
    }
    cout << t->x << '\n';
    print_treap_recursive_with_depth(t->right, depth + 1);
}

void print_treap(Node* root) {
    print_treap_recursive(root);
    cout << '\n';
}


void print_treap_with_depth(Node* root) {
    print_treap_recursive_with_depth(root, 0);
    cout << '\n';
}