Treap

2014.12.31 10:37 Wed| 4 visits oi_2015| 2015_刷题日常| Text

昨天做某一道树套树结果被卡常数T到死……QAQ

还是写了一个Treap模板……貌似真的比Splay好写?

第二个模板貌似比第一个模板省心了好多……

namespace Treap
{
    template<typename _Tp> class treap_node;
    template<typename _Tp> class treap;
    template<typename _Tp>
        class treap_node
    {
        private:
            typedef treap_node<_Tp> node;
            _Tp val;
            int cnt, size, key;
            node *son[2];

        public:
            friend class treap<_Tp>;

            treap_node()
            : val(), cnt(), size(), key(rand()), son() { }

            treap_node(const _Tp &_v, node *nil, int _c = 0)
            : val(_v), cnt(_c), size(_c), key(rand()), son()
            { son[0] = son[1] = nil; }

            inline void pushup()
            { size = son[0]->size + son[1]->size + cnt; }
    };

    template<typename _Tp>
        class treap
    {
        private:
            typedef treap_node<_Tp> node;
            typedef treap<_Tp>      tree;
            node *nil, *root;
            _Tp def;

        public:
            treap() : nil(), root(), def()
            { root = nil = new node(); }

            treap(const _Tp f) : nil(), root(), def(f)
            { root = nil = new node(); }

            inline int size() { return root->size; }

            inline void insert(_Tp val, int c = 1)
            { insert(root, val, c); }

            inline void erase(_Tp val, int c = 1)
            { erase(root, val, c); }

            inline int find(_Tp val)
            { return find(root, val) + 1; }

            inline _Tp rank(int k)
            { return rank(root, k); }

            inline _Tp prec(_Tp val)
            {
                node *temp = prec(root, val);
                return temp == nil ? def : temp->val;
            }

            inline _Tp succ(_Tp val)
            {
                node *temp = succ(root, val);
                return temp == nil ? def : temp->val;
            }

            void rotate(node *&x, int d)
            {
                node *k = x->son[!d];
                x->son[!d] = k->son[d];
                k->son[d] = x;
                x->pushup(); k->pushup();
                x = k;
            }

            void get_seq(node *x, vector< pair<_Tp, int> > &p)
            {
                if(x == nil) return;
                get_seq(x->son[0], p);
                p.push_back(make_pair(x->val, x->cnt));
                get_seq(x->son[1], p);
            }

            void insert(node *&x, _Tp val, int c = 1)
            {
                if(x == nil)
                    x = new node(val, nil, c);
                else if(val == x->val)
                    x->cnt += c;
                else
                {
                    int d = x->val < val;
                    insert(x->son[d], val, c);
                    if(x->son[d]->key > x->key)
                        rotate(x, d^1);
                }
                x->pushup();
            }

            void insert(tree &t)
            {
                vector< pair<_Tp, int> > p;
                typename vector< pair<_Tp, int> >::iterator it;
                t.get_seq(t.root, p);
                for(it = p.begin(); it != p.end(); ++it)
                    insert(root, it->first, it->second);
            }

            void erase(node *&x, _Tp val, int c = 1)
            {
                if(val == x->val)
                {
                    x->cnt -= c;
                    if(x->cnt <= 0)
                    {
                        if(x->son[0] == nil) x = x->son[1];
                        else if(x->son[1] == nil) x = x->son[0];
                        else
                        {
                            int d = x->son[0]->key > x->son[1]->key;
                            rotate(x, d);
                            erase(x->son[d], val, c);
                        }
                    }
                }
                else erase(x->son[val > x->val], val, c);
                if(x != nil) x->pushup();
            }

            int find(node *x, _Tp val)
            {
                if(x == nil) return 0;
                if(val <= x->val)
                    return find(x->son[0], val);
                return find(x->son[1], val) + x->cnt + x->son[0]->size;
            }

            _Tp rank(node *x, int k)
            {
                if(k <= x->son[0]->size)
                    return rank(x->son[0], k);
                k -= x->son[0]->size;
                if(k <= x->cnt) return x->val;
                return rank(x->son[1], k - x->cnt);
            }

            node *prec(node *x, const _Tp &val)
            {
                if (x == nil) return x;
                int d = val <= x->val ? 0 : 1;
                if (!d) return prec(x->son[0], val);
                node *re = prec(x->son[1], val);
                return re == nil ? x : re;
            }

            node *succ(node *x, const _Tp &val)
            {
                if (x == nil) return x;
                int d = val < x->val ? 0 : 1;
                if (d) return succ(x->son[1], val);
                node *re = succ(x->son[0], val);
                return re == nil ? x : re;
            }

            friend ostream &operator << (ostream &out, tree &x)
            {
                vector< pair<_Tp, int> > p;
                typename vector< pair<_Tp, int> >::iterator it;
                x.get_seq(x.root, p); cout<<'{';
                for(it = p.begin(); it != p.end(); ++it)
                    out<<'('<<it->first<<','<<it->second<<')';
                out<<'}';
                return out;
            }
    };
}