Splay 模板

雾

/*
 * by
 *      skip2004
 *  Splay Tree
 */
 
#include <iostream>
#include <algorithm>
#include <cstring>
#include <random>
#include <string>
#include <cstdio>
#include <ctime>

namespace Splay{
    
    #define ERROR_CHECK(condition,ERROR) if(__builtin_expect(condition,0)) puts(ERROR), exit(0);
    
    template<typename _Tp, typename _Cmp = std::less<_Tp>>
    class Splay_Node;
    
    template<typename _Tp, typename _Cmp = std::less<_Tp>>
    class Splay_Tree;
    
    template<typename _Tp, typename _Cmp>
    class Splay_Node{
        private:
            
            Splay_Node * left_son, * right_son, * father;
            _Tp value;
            size_t size;
            inline void clear();    
            inline void left_rotate();  
            inline void right_rotate();
        public: 
        
            inline bool is_left_son() const;
            inline bool is_right_son() const;
            inline bool is_root() const;
            inline void update();
            inline void rotate();
            inline _Tp kth_element(size_t k,Splay_Tree<_Tp,_Cmp> * tree);
            inline size_t get_size() const;
            inline _Tp get_value() const;
            inline Splay_Node(_Tp value);
            inline Splay_Node *& get_left_son();
            inline Splay_Node *& get_right_son();
            inline Splay_Node *& get_father();
    };
    
    template<typename _Tp, typename _Cmp>
    class Splay_Tree
    {
        private:
            const _Cmp& cmp = _Cmp{};
            Splay_Node<_Tp,_Cmp> * root;
            inline void insert(Splay_Node<_Tp,_Cmp> * oth);
        public:
            
            inline void splay(Splay_Node<_Tp,_Cmp> * node);
            inline Splay_Tree(Splay_Node<_Tp,_Cmp> * root = nullptr);
            inline void insert(_Tp value);
            inline void erase(_Tp value);
            inline Splay_Node<_Tp,_Cmp> * lower_bound(_Tp value);
            inline Splay_Node<_Tp,_Cmp> * upper_bound(_Tp value);
            inline size_t lower(_Tp value);
            inline size_t less_than(_Tp value);
            inline size_t get_rank(_Tp value);
            inline _Tp kth_element(size_t k);
            inline size_t size() const;
            inline bool empty() const;
            inline _Tp predecessor(_Tp value);
            inline _Tp successor(_Tp value);    
    };
    
    
    template<typename _Tp, typename _Cmp>
        inline void Splay_Node<_Tp,_Cmp>::clear()
        {
            if(left_son != nullptr)
            {
                this -> left_son -> clear();
            }
            if(right_son != nullptr)
            {
                this -> right_son -> clear();
            }
            delete this;
        }
        
    template<typename _Tp, typename _Cmp>
        inline bool Splay_Node<_Tp, _Cmp>::is_left_son() const
        {
            return this -> father != nullptr && this == father -> left_son;
        }
        
    template<typename _Tp, typename _Cmp>
        inline bool Splay_Node<_Tp, _Cmp>::is_right_son() const
        {
            return this -> father != nullptr && this == father -> right_son;
        }
        
    template<typename _Tp,typename _Cmp>
        inline bool Splay_Node<_Tp,_Cmp>::is_root() const 
        {
            return this -> father == nullptr;
        }
        
    template<typename _Tp,typename _Cmp>
        inline void Splay_Node<_Tp,_Cmp>::update()
        {
            this -> size = 1;
            if(left_son != nullptr) this -> size += left_son -> size;
            if(right_son != nullptr) this -> size += right_son -> size;
        }
        
    template<typename _Tp,typename _Cmp>
        inline void Splay_Node<_Tp,_Cmp>::left_rotate()
        {
            ERROR_CHECK(father == nullptr,"No father !");
            Splay_Node * fa = father, * grand_father = fa -> father;
            if(grand_father != nullptr)
            {
                if(father -> is_left_son())
                    grand_father -> left_son = this;
                else
                    grand_father -> right_son = this;
            }
            fa -> right_son = this -> left_son;
            this -> left_son = fa;
            if(fa -> right_son != nullptr)
                fa -> right_son -> father = fa;
            fa -> father = this;
            this -> father = grand_father;
            fa -> update();
        }
        
    template<typename _Tp,typename _Cmp>
        inline void Splay_Node<_Tp,_Cmp>::right_rotate()
        {
            ERROR_CHECK(father == nullptr,"No father !");
            Splay_Node * fa = father, * grand_father = fa -> father;
            if(grand_father != nullptr)
            {
                if(father -> is_left_son())
                    grand_father -> left_son = this;
                else
                    grand_father -> right_son = this;
            }
            fa -> left_son = this -> right_son;
            this -> right_son = fa;
            if(fa -> left_son != nullptr)
                fa -> left_son -> father = fa;
            fa -> father = this;
            this -> father = grand_father;
            fa -> update();
        }
        
    template<typename _Tp,typename _Cmp>
        inline void Splay_Node<_Tp,_Cmp>::rotate()
        {
            if(this -> is_left_son())
                right_rotate();
            else
                left_rotate();
        }
        
    template<typename _Tp,typename _Cmp>
        inline _Tp Splay_Node<_Tp,_Cmp>::kth_element(size_t k,Splay_Tree<_Tp,_Cmp> * tree)
        {
            const size_t left_son_size = this -> left_son == nullptr ? 0 : this -> left_son -> size;
            if(left_son_size >= k) 
                return this -> left_son -> kth_element(k,tree);
            if(left_son_size + 1 == k)
            {
                tree -> splay(this);
                return this -> value;
            }
            return this -> right_son -> kth_element(k - left_son_size - 1,tree);
        }
        
    template<typename _Tp,typename _Cmp>
        inline size_t Splay_Node<_Tp,_Cmp>::get_size() const
        {
            return this -> size;
        }
        
    template<typename _Tp,typename _Cmp>
        inline _Tp Splay_Node<_Tp,_Cmp>::get_value() const
        {
            return this -> value;
        }
        
    template<typename _Tp,typename _Cmp>
        inline Splay_Node<_Tp,_Cmp>::Splay_Node(_Tp value)
        {
            left_son = right_son = father = nullptr;
            this -> value = value, size = 1;
        }
        
    template<typename _Tp,typename _Cmp>
        inline Splay_Node<_Tp,_Cmp> *& Splay_Node<_Tp,_Cmp>::get_left_son()
        {
            return this -> left_son;
        }
        
    template<typename _Tp,typename _Cmp>
        inline Splay_Node<_Tp,_Cmp> *& Splay_Node<_Tp,_Cmp>::get_right_son()
        {
            return this -> right_son;
        }
        
    template<typename _Tp,typename _Cmp>
        inline Splay_Node<_Tp,_Cmp> *& Splay_Node<_Tp,_Cmp>::get_father()
        {
            return this -> father;
        }
    
    
    template<typename _Tp,typename _Cmp>
        inline void Splay_Tree<_Tp,_Cmp>::splay(Splay_Node<_Tp,_Cmp> * node)
        {
            for(;!node -> is_root();node -> rotate())
                if(!node -> get_father() -> is_root())
                {
                    if(node -> is_left_son()  ^ node -> get_father() -> is_left_son())
                        node -> rotate();
                    else
                        node -> get_father() -> rotate();
                }
            node -> update();
            root = node;
        }
        
    template<typename _Tp,typename _Cmp>
        inline void Splay_Tree<_Tp,_Cmp>::insert(Splay_Node<_Tp,_Cmp> * oth)
        {
            if(oth == nullptr)
                return ;
            if(root == nullptr)
                root = oth;
            else
            {
                Splay_Node<_Tp,_Cmp> * now = root;
                while(true)
                {
                    if(cmp(oth -> get_value(),now -> get_value()))
                        if(now -> get_left_son() == nullptr)
                        {
                            now -> get_left_son() = oth;
                            oth -> get_father() = now;
                            splay(now -> get_left_son());
                            return ;
                        }
                        else
                            now = now -> get_left_son();
                    else
                        if(now -> get_right_son() == nullptr)
                        {
                            now -> get_right_son() = oth;
                            oth -> get_father() = now;
                            splay(now -> get_right_son());
                            return ;
                        }
                        else
                            now = now -> get_right_son();
                }
            }
        }
        
    template<typename _Tp,typename _Cmp>
        inline Splay_Tree<_Tp,_Cmp>::Splay_Tree(Splay_Node<_Tp,_Cmp> * root)
        {
            this -> root = root;
        }
        
    template<typename _Tp,typename _Cmp>
        inline void Splay_Tree<_Tp,_Cmp>::insert(_Tp value)
        {
            insert(new Splay_Node<_Tp,_Cmp>(value));
        }
        
    template<typename _Tp,typename _Cmp>
        inline void Splay_Tree<_Tp,_Cmp>::erase(_Tp value)
        {
            Splay_Node<_Tp,_Cmp> * now = root;
            while(now != nullptr)
            {
                if(cmp(now -> get_value(),value))
                    now = now -> get_right_son();
                else
                    if(cmp(value, now -> get_value()))
                        now = now -> get_left_son();
                    else 
                    {
                        splay(now);
                        if(now -> get_left_son() != nullptr)
                            now -> get_left_son() -> get_father() = nullptr;
                        if(now -> get_right_son() != nullptr)
                            now -> get_right_son() -> get_father() = nullptr;
                        root = now -> get_left_son();
                        insert(now -> get_right_son());
                        return ;
                    }
            }
            throw "Error in function : erase";
        }
        
    template<typename _Tp,typename _Cmp>
        inline Splay_Node<_Tp,_Cmp> * Splay_Tree<_Tp,_Cmp>::lower_bound(_Tp value)
        {
            Splay_Node<_Tp,_Cmp> * now = root, * ans = nullptr;
            while(now != nullptr)
            {
                if(cmp(now -> get_value(),value))
                {
                    if(!now -> get_right_son())
                    {
                        splay(now);
                        break;
                    }
                    now = now -> get_right_son();
                }
                else
                {
                    ans = now;
                    if(!now -> get_left_son())
                    {
                        splay(now);
                        break; 
                    } 
                    now = now -> get_left_son();
                }
            }
            return ans;
        }
        
    template<typename _Tp,typename _Cmp>
        inline Splay_Node<_Tp,_Cmp> * Splay_Tree<_Tp,_Cmp>::upper_bound(_Tp value)
        {
            Splay_Node<_Tp,_Cmp> * now = root, * ans = nullptr;
            while(now != nullptr)
            {
                if(cmp(value,now -> get_value()))
                {
                    ans = now;
                    if(!now -> get_left_son())
                    {
                        splay(now);
                        break;
                    }
                    now = now -> get_left_son();
                }
                else
                {
                    if(!now -> get_right_son())
                    {
                        splay(now);
                        break;
                    }
                    now = now -> get_right_son();
                }
            }
            return ans;
        }
        
    template<typename _Tp,typename _Cmp>
        inline size_t Splay_Tree<_Tp,_Cmp>::lower(_Tp value)
        {
            if(root == nullptr)
                return 0;
            Splay_Node<_Tp,_Cmp> * node = this -> upper_bound(value);
            if(node == nullptr)
                return root -> get_size();
            splay(node);
            if(node -> get_left_son() == nullptr)
                return 0;
            return node -> get_left_son() -> get_size();
        }
        
    template<typename _Tp,typename _Cmp>
        inline size_t Splay_Tree<_Tp,_Cmp>::less_than(_Tp value)
        {
            if(root == nullptr)
                return 0;
            Splay_Node<_Tp,_Cmp> * node = this -> lower_bound(value);
            if(node == nullptr)
                return root -> get_size();
            splay(node);
            if(node -> get_left_son() == nullptr)
                return 0;
            return node -> get_left_son() -> get_size();
        }
        
    template<typename _Tp,typename _Cmp>
        inline size_t Splay_Tree<_Tp,_Cmp>::get_rank(_Tp value)
        {
            return less_than(value) + 1;
        }
        
    template<typename _Tp,typename _Cmp>
        inline _Tp Splay_Tree<_Tp,_Cmp>::kth_element(size_t k)
        {
            ERROR_CHECK(root == nullptr,"Error: No element in the Splay Tree. ");
            ERROR_CHECK(k < 1 || k > this -> size(),"Error: K is out of range !");
            return root -> kth_element(k,this);
        }
        
    template<typename _Tp,typename _Cmp>
        inline size_t Splay_Tree<_Tp,_Cmp>::size() const
        {
            if(root == nullptr)
                return 0;
            else
                return root -> get_size();
        }
    
    template<typename _Tp,typename _Cmp>
        inline bool Splay_Tree<_Tp,_Cmp>::empty() const
        {
            return root == nullptr;
        }
        
    template<typename _Tp,typename _Cmp>
        inline _Tp Splay_Tree<_Tp,_Cmp>::predecessor(_Tp value)
        {
            return kth_element(less_than(value));
        }
        
    template<typename _Tp,typename _Cmp>
        inline _Tp Splay_Tree<_Tp,_Cmp>::successor(_Tp value)
        {
            return kth_element(lower(value) + 1);
        }
    
}

Splay::Splay_Tree<int> tree;
int x,ch,flag;
inline int read()
{
    while(isspace(ch=getchar())); flag = 0;
    if(ch == 45) ch = getchar(), flag = 1; x = ch & 15;
    while(isdigit(ch=getchar())) x = x * 10 + (ch&15);
    return flag ? - x : x;
}
int main()
{
    std::ios::sync_with_stdio(false), std::cin.tie(0);
    std::ios::sync_with_stdio(false), std::cin.tie(0);
    int n = read();
    for(int i = 1; i <= n; ++i)
    {
        int opt = read(), x = read();
        switch(opt)
        {
            case 1:
                {
                    tree.insert(x);
                    break;
                }
            case 2:
                {
                    tree.erase(x);
                    break;
                }
            case 3:
                {
                    std::cout << tree.get_rank(x) << '\n' ;
                    break;
                }
            case 4:
                {
                    std::cout << tree.kth_element(x) << '\n';
                    break;
                }
            case 5:
                {
                    std::cout << tree.predecessor(x) << '\n';
                    break;
                } 
            case 6:
                {
                    std::cout << tree.successor(x)  << '\n';
                    break;
                }
        }
    }
}

Splay 模板

原文：https://www.cnblogs.com/skip1978/p/11169097.html