#include <memory>//智能指针头文件

 #include <random>//随机数头文件

 #include <iostream>

 #include <algorithm>

 #include <ctime>//time头文件

 template<class T>

 struct node

 {

     T key;

     unsigned weight;

     std::shared_ptr<node<T>> lchild, rchild, parent;

     node(T key, unsigned weight, std::shared_ptr<node<T>> lchild = nullptr,

         std::shared_ptr<node<T>> rchild = nullptr, std::shared_ptr<node<T>> parent = nullptr):

         key(key)

     {

         this->weight = weight;

         this->lchild = lchild;

         this->rchild = rchild;

         this->parent = parent;

     }

 };

 template<class T>

 class Treap

 {

 private:

     std::shared_ptr<node<T>> root;

     std::default_random_engine generator;

     std::uniform_int_distribution<int> dis;

     void left_rotation(std::shared_ptr<node<T>> a)

     {

         if (a == nullptr) return;

         std::shared_ptr<node<T>> b = a->lchild;

         if (b == nullptr) return;

         if (b->rchild != nullptr)

         {

             a->lchild = b->rchild;

             b->rchild->parent = a;

         }

         else

             a->lchild = nullptr;//

         b->parent = a->parent;

         if (a->parent == nullptr)

             root = b;

         else

         {

             if (a->parent->lchild == a)

                 a->parent->lchild = b;

             else

                 a->parent->rchild = b;

         }

         b->rchild = a;

         a->parent = b;

     }

     void right_rotation(std::shared_ptr<node<T>> a)

     {

         if (a == nullptr) return;

         std::shared_ptr<node<T>> b = a->rchild;

         if (b == nullptr) return;

         if (b->lchild != nullptr)

         {

             a->rchild = b->lchild;

             b->lchild->parent = a;

         }

         else

             a->rchild = nullptr;

         b->parent = a->parent;

         if (a->parent == nullptr)

             root = b;

         else

         {

             if (a->parent->lchild == a)

                 a->parent->lchild = b;

             else

                 a->parent->rchild = b;

         }

         b->lchild = a;

         a->parent = b;

     }

 public:

     Treap() :generator(time(nullptr)), dis(, )

     {

         root = nullptr;

     }

     void insert(T key)

     {

         std::shared_ptr<node<T>> tmp = std::make_shared<node<T>>(key, dis(generator));

         std::shared_ptr<node<T>> ptr = root;

         if (ptr == nullptr)

         {

             root = tmp;

             return;

         }

         while (true)

         {

             if (key <= ptr->key)

             {

                 if (ptr->lchild == nullptr) break;

                 ptr = ptr->lchild;

             }

             else

             {

                 if (ptr->rchild == nullptr) break;

                 ptr = ptr->rchild;

             }

         }

         if (key <= ptr->key)

             ptr->lchild = tmp;

         else

             ptr->rchild = tmp;

         tmp->parent = ptr;

         while (ptr != nullptr)

         {

             if (tmp->weight < ptr->weight)

             {

                 if (ptr->lchild == tmp)

                 {

                     left_rotation(ptr);

                     ptr = tmp->parent;

                 }

                 else

                 {

                     right_rotation(ptr);

                     ptr = tmp->parent;

                 }

             }

             else

                 break;

         }

     }

     void earse(T key)

     {

         std::shared_ptr<node<T>> ptr = root;

         while (ptr != nullptr)

         {

             if (key == ptr->key)

                 break;

             else if (key < ptr->key)

                 ptr = ptr->lchild;

             else

                 ptr = ptr->rchild;

         }

         if (ptr == nullptr) return;

         while (true)

         {

             if (ptr->lchild == nullptr || ptr->rchild == nullptr)

             {

                 if (ptr->lchild == nullptr && ptr->rchild == nullptr)

                 {

                     if (ptr->parent == nullptr) root = nullptr;

                     else

                     {

                         if (ptr->parent->lchild == ptr)

                             ptr->parent->lchild = nullptr;

                         else

                             ptr->parent->rchild = nullptr;

                     }

                 }

                 else if (ptr->lchild == nullptr)

                 {

                     if (ptr->parent == nullptr)

                         root = ptr->rchild;

                     else

                     {

                         if (ptr->parent->lchild == ptr)

                             ptr->parent->lchild = ptr->rchild;

                         else

                             ptr->parent->rchild = ptr->rchild;

                     }

                     ptr->rchild->parent = ptr->parent;

                 }

                 else

                 {

                     if (ptr->parent == nullptr)

                         root = ptr->lchild;

                     else

                     {

                         if (ptr->parent->lchild == ptr)

                             ptr->parent->lchild = ptr->lchild;

                         else

                             ptr->parent->rchild = ptr->lchild;

                     }

                     ptr->lchild->parent = ptr->parent;

                 }

                 return;

             }

             else

             {

                 if (ptr->lchild->weight <= ptr->rchild->weight)

                     left_rotation(ptr);

                 else

                     right_rotation(ptr);

             }

         }

     }

 };