Splay tree

#pragma GCC optimize ("Ofast,unroll-loops")
#pragma GCC target ("avx2,fma")
#include<bits/stdc++.h>

#include <utility>
using namespace std;


//rope
#define forx(i,a,b) for (int i = a; i < b; i++)
#define INF int(1e9)
#define all(x2) begin(x2),end(x2)
#define isz(t) ((ll)(t.size()))
#define last(x) (*(x.end()-1))
#define mod ll(1e9+7)
#define ft first
#define sd second
#define pr pair
#define sh(x) false //cerr<<#x<<" = "<<x<<'\n'
//#define debug

using ll= long long;//
using ld= long double;
using ull=unsigned long long;
using ii = pair<ll, ll>;
string to_string(string s){
    return s;
}
template<typename T>
ostream& print_range(ostream& os,T begin,T end){
    for(auto it=begin;it!=end;++it)
        os<<*it<<' ';
    os<<'\n';
    return os;
}
template<typename ...T>
ostream& operator<<(ostream& os,const vector<T...>&v){
    return print_range(os,v.begin(),v.end());
}
template<typename ...Args>
void printer(Args&&... args) {
    (std::cerr << ... <<( to_string(args)+" ")) << '\n';
}

template<typename T, typename... Args>
void push_back_vec(std::vector<T>& v, Args&&... args)
{
    (v.push_back(std::forward<Args>(args)), ...);
}
template<class ...Args>
void input(Args&... args) {
    (cin>>...>>args);
}
template<typename T>
T minimum(T x) {
    return x;
}

template<typename T, typename... Pack>
auto minimum(T x, Pack... p) {
    using common = typename std::common_type<T, Pack...>::type;
    return std::min((common)x, (common)minimum(p...));
}

template<typename T>
T maximum(T x) {
    return x;
}

template<typename T, typename... Pack>
auto maximum(T x, Pack... p) {
    using common = typename std::common_type<T, Pack...>::type;
    return std::max((common)x, (common)maximum(p...));
}
class splay_tree{
    class node{
    public:
        int key;
        node *left, *right;
        node(int key) : key(key),left(nullptr),right(nullptr){}
    };
    node *tree_root;

    // Эта функция поднимет ключ
    // в корень, если он присутствует в дереве.
    // Если такой ключ отсутствует в дереве, она
    // поднимет в корень самый последний элемент,
    // к которому был осуществлен доступ.
    // Эта функция изменяет дерево
    // и возвращает новый корень (root).
    node *rightRotate(node *x)
    {
        node *y = x->left;
        x->left = y->right;
        y->right = x;
        return y;
    }

    // Служебная функция для разворота поддерева с корнем x влево
    // Смотрите диаграмму, приведенную выше.
    node *leftRotate(node *x)
    {
        node *y = x->right;
        x->right = y->left;
        y->left = x;
        return y;
    }
    // Эта функция поднимет ключ
    // в корень, если он присутствует в дереве.
    // Если такой ключ отсутствует в дереве, она
    // поднимет в корень самый последний элемент,
    // к которому был осуществлен доступ.
    // Эта функция изменяет дерево
    // и возвращает новый корень (root).
    node *splay(node *root, int key)
    {
        // Базовые случаи: root равен NULL или
        // ключ находится в корне
        if (root == nullptr || root->key == key)
            return root;

        // Ключ лежит в левом поддереве
        if (root->key > key)
        {
            // Ключа нет в дереве, мы закончили
            if (root->left == nullptr) return root;

            // Zig-Zig (Левый-левый)
            if (root->left->key > key)
            {
                // Сначала рекурсивно поднимем
                // ключ как корень left-left
                root->left->left = splay(root->left->left, key);

                // Первый разворот для root,
                // второй разворот выполняется после else
                root = rightRotate(root);
            }
            else if (root->left->key < key) // Zig-Zag (Левый-правый)
                {
                // Сначала рекурсивно поднимаем
                // ключ как корень left-right
                root->left->right = splay(root->left->right, key);

                // Выполняем первый разворот для root->left
                if (root->left->right != nullptr)
                    root->left = leftRotate(root->left);
                }

            // Выполняем второй разворот для корня
            return (root->left == nullptr)? root: rightRotate(root);
        }
        else // Ключ находится в правом поддереве
        {
            // Ключа нет в дереве, мы закончили
            if (root->right == nullptr) return root;

            // Zag-Zig (Правый-левый)
            if (root->right->key > key)
            {
                // Поднять ключ как корень right-left
                root->right->left = splay(root->right->left, key);

                // Выполняем первый поворот для root->right
                if (root->right->left != nullptr)
                    root->right = rightRotate(root->right);
            }
            else if (root->right->key < key)// Zag-Zag (Правый-правый)
                {
                // Поднимаем ключ как корень
                // right-right и выполняем первый разворот
                root->right->right = splay(root->right->right, key);
                root = leftRotate(root);
                }

            // Выполняем второй разворот для root
            return (root->right == nullptr)? root: leftRotate(root);
        }
    }
    // Служебная функция для вывода
    // обхода в дерева ширину.
    // Функция также выводит высоту каждого узла
    void preOrder(node *root)
    {
        if (root != nullptr)
        {
            preOrder(root->left);
            cout<<root->key<<" ";
            preOrder(root->right);
        }
    }
    pair<node*,node*> split(node* root,int key){
        if(root==nullptr){
            return{nullptr,nullptr};
        }
        root=splay(root,key);
        if(root->key<key){
            auto right=root->right;
            root->right=nullptr;
            return {root,right};
        }
        else{
            auto left=root->left;
            root->left=nullptr;
            return {left,root};
        }
    }
    node* merge(node* left,node* right){
        if(left==nullptr)
            return right;
        if(nullptr==right)
            return left;
        node* root=left;
        while(root->right!=nullptr)
            root=root->right;
        root=splay(left,root->key);
        root->right=right;
        return root;
    }
    public:
    splay_tree():tree_root(nullptr){}
    void insert(int key){
        auto[left,right]=split(tree_root,key);
        tree_root=new node(key);
        tree_root->left=left;
        tree_root->right=right;
    }
    void erase(int key){
        auto root=splay(tree_root,key);
        tree_root= merge(root->left,root->right);
    }
    void couter(){
        preOrder(tree_root);
        cout<<'\n';
    }
    bool contains(int key){
        tree_root=splay(tree_root,key);
        return nullptr!=tree_root && tree_root->key==key;
    }
};

int  main() {
//    d[i][j]=d[i+1][j-1] +2* s[i]==s[j]
//    d[i][j]=наибольшая подпоследовательность-палиндром на отрезке  i j
//    if s[i]==s[j] then remax(d[i][j],d[i+1][j-1] +2)
//    remax(d[i][j], d[i + 1][j])
//    remax(d[i][j], d[i][j - 1])
//    ios::sync_with_stdio(false);
//    cin.tie(nullptr);
//    cout.tie(nullptr);
//    cout.setf(ios::fixed);
//    cout.precision(15);
//    solution();
    splay_tree tr;
    for(int i: vector<int>{100,50,200,40,30,20}){
        tr.insert(i);
    }
    tr.couter();
    cout<<tr.contains(50)<<'\n';
    tr.erase(50);
    cout<<tr.contains(50)<<'\n';
    tr.couter();
    cout<<tr.contains(150)<<'\n';
    tr.insert(150);
    cout<<tr.contains(150)<<'\n';
    tr.couter();
}