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

mt19937 gen(time(0));

struct Node {
    int x, y, size;

    Node* left, * right;

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

    ~Node() {
        if (left) {
            delete left;
        }
        if (right) {
            delete right;
        }
    }
};

int node_size(Node* t) {
    if (t == nullptr) {
        return 0;
    }
    return t->size;
}

void update(Node* t) {
    if (t == nullptr) {
        return;
    }
    t->size = node_size(t->left) + node_size(t->right) + 1;
}

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;
        update(t);
        return { t, split_right.second };
    }
    else {
        auto split_left = split(t->left, x);
        t->left = split_left.second;
        update(t);
        return { split_left.first, t };
    }
}


pair<Node*, Node*> split_size(Node* t, int sz) {
    // Делим элементы t на два дерева так, чтобы в первом дереве было
    // sz элементов, а во втором --- все остальные.
    // 
    // Если в t меньше sz элементов, то все элементы будут в первом
    // дереве, а второе будет пустым.
    if (t == nullptr) {
        return { nullptr, nullptr };
    }
    if (node_size(t->left) < sz) {
        auto split_right = split_size(t->right, sz - node_size(t->left) - 1);
        t->right = split_right.first;
        update(t);
        return { t, split_right.second };
    }
    else {
        auto split_left = split_size(t->left, sz);
        t->left = split_left.second;
        update(t);
        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);
        update(l);
        return l;
    }
    else {
        r->left = merge(l, r->left);
        update(r);
        return r;
    }
}



Node* insert(Node* t, int x) {
    auto split_tree = split(t, x);
    Node* right = merge(new Node(x), split_tree.second);
    return merge(split_tree.first, right);
}






Node* remove(Node* t, int x) {
    auto split_tree = split(t, x);
    auto split_left = split(split_tree.first, x - 1);
    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);
    }
}

int nth_element_treap(Node*& t, int n) {
    auto split_treap = split_size(t, n);
    // В split_treap.first n элементов.
    // n-ая порядковая статистика — это самый левый элемент
    // split_treap.second.
    auto split_right = split_size(split_treap.second, 1);
    int result = split_right.first->x;
    t = merge(split_treap.first, merge(split_right.first, split_right.second));
    return result;
}


int nth_element_recursive(Node* t, int ind) {
    if (t == nullptr) {
        return -1;
    }
    if (node_size(t->left) == ind) {
        return t->x;
    }
    if (node_size(t->left) < ind) {
        return nth_element_recursive(t->right, ind - node_size(t->left) - 1);
    }
    else {
        return nth_element_recursive(t->left, ind);
    }
}



void print_node(Node* t) {
    cout << t->x << '|' << t->size;
}

void print_treap_recursive(Node* t) {
    if (t == nullptr) {
        return;
    }
    cout << "(";
    print_treap_recursive(t->left);
    print_node(t);
    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 << ".";
    }
    print_node(t);
    cout << '\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';
}