无旋Treap模板
小菜鸟
2020-07-29 15:45:16
### 真·无旋Treap模板
为了方便地重用代码，C++有了模板和多态功能。
然而OIer一般并不会花时间写这些
（除了我这种实际上已经AFO的人
这个板子喜欢的可以拿去用...出锅了~~概不负责~~私信我改awa
---
码风最早是学习了P3369题解中的红黑树代码，后来参考了`GNU STL`和自己的偏好，基本固定了写大模板的风格。
---
再简单讲一讲Treap的思想
Treap是一种基于随机化的自平衡二叉搜索树。为了避免二叉搜索树在精心构造的数据下退化，Treap给每个结点增加了一个随机权值，并设法使随机权值满足堆的性质。~~将命运掌握在了自己手中~~
常见的Treap通过插入、删除结点后进行旋转来维持其性质。然而由于Treap的性质简单而容易维护，Treap可以容易地在$O(log_2 n)$的时间内分裂成两棵值域不相交的Treap，两棵不相交的Treap也可以在相同时间内合并。
于是国内一位叫做fhq的神仙据此给出了Treap依赖于分裂、合并的一种实现，以牺牲一定运行效率的代价，换取了相对简洁的代码和更加灵活的功能，使得Treap可以维护区间信息。
---
然而Treap怎么打并不是重点，模板才是。
为了能够在日后日常做题中避免反复打模板，干脆花了一上午敲了一个封装好的板子，也算是锻炼码力。
~~并且这也是我第一次完全用自己的代码写完普通平衡树~~
功能和`std::set`基本相同，实现了一个不可重集合，支持`set`支持的各类查找操作并支持了查询元素排名和按排名查询（当然效率比起红黑树低一些
一些细小的函数懒得实现，，，
---
代码（底下有说明，代码可以先略过不看）
~~怎么比我封装好的LCT还长不少~~
```cpp
#ifndef TREAP_TEMPLATE //Treap template
#define TREAP_TEMPLATE
#if __cplusplus>=201103L
#include<random>
#endif
#if __cplusplus<201103L
#ifdef nullptr
#undef nullptr
#endif
#define nullptr NULL
#endif
template<typename _Tp,typename _Cmp=std::less<_Tp>,typename _Alloc=std::allocator<_Tp> >
class treap:_Cmp
{
public:
typedef _Tp Value_type;
typedef _Cmp Comparator_type;
typedef size_t size_type;
typedef _Alloc alloc_type;
#if __cplusplus>=201103L
typedef typename std::allocator_traits<_Alloc> alloc_traits_type;
#endif
private:
struct Node;
Node *end_node;
Node *&root;
inline Node *__get_new_node(_Tp);
inline void __emplace_node(Node*,_Tp);
inline void __delete_node(Node*);
Node *merge(Node*,Node*);
void split_val(Node*,const _Tp&,Node*&,Node*&);
void split_val_equal(Node*,const _Tp&,Node*&,Node*&);
inline static unsigned long long get_pri();
void destroy_inner_nodes(Node*);
typedef typename _Alloc::template rebind<Node>::other _node_alloc_type;
#if __cplusplus>=201103L
typedef typename alloc_traits_type::template rebind_traits<Node> _node_alloc_traits_type;
#endif
_node_alloc_type _node_allocator;
public:
struct iterator;
treap():
end_node(new Node),
root(end_node->lc)
{}
~treap();
std::pair<iterator,bool> insert(const _Tp&);
bool erase(const _Tp&);
iterator begin()const;
iterator end()const;
iterator find(const _Tp&)const;
iterator lower_bound(const _Tp&)const;
iterator upper_bound(const _Tp&)const;
iterator find_by_order(const size_type&)const;
size_type order_of_key(const _Tp&)const;
size_type size()const;
};
template<typename _Tp,typename _Cmp,typename _Alloc>
struct treap<_Tp,_Cmp,_Alloc>::Node
{
_Tp value;
unsigned long long pri;
size_type s;
Node *lc,*rc,*ftr;
Node():
pri(get_pri()),
s(1),
lc(nullptr),
rc(nullptr),
ftr(nullptr)
{}
Node(_Tp val):
value(val),
pri(rand()),
s(1),
lc(nullptr),
rc(nullptr),
ftr(nullptr)
{}
void maintain()
{
s=1;
if(lc!=nullptr)
{
s+=lc->s;
lc->ftr=this;
}
if(rc!=nullptr)
{
s+=rc->s;
rc->ftr=this;
}
}
inline void rotate()
{
Node *nftr=ftr,*gftr=ftr->ftr;
if(gftr!=nullptr)
{
if(nftr==gftr->lc)gftr->lc=this;
else gftr->rc=this;
}
if(this==nftr->lc)
{
nftr->lc=rc;
rc=nftr;
}
else
{
nftr->rc=lc;
lc=nftr;
}
nftr->maintain();
maintain();
if(gftr!=nullptr)gftr->maintain();
}
};
template<typename _Tp,typename _Cmp,typename _Alloc>
inline
typename treap<_Tp,_Cmp,_Alloc>::Node*
treap<_Tp,_Cmp,_Alloc>::__get_new_node(_Tp __value)
{
#if __cplusplus>=201103L
Node *new_ptr=_node_alloc_traits_type::allocate(_node_allocator,1);
_node_alloc_traits_type::construct(_node_allocator,new_ptr,__value);
#else
Node *new_ptr=_node_allocator.allocate(1);
_node_allocator.construct(new_ptr,__value);
#endif
return new_ptr;
}
template<typename _Tp,typename _Cmp,typename _Alloc>
inline
void
treap<_Tp,_Cmp,_Alloc>::__delete_node(Node *__ptr)
{
#if __cplusplus>=201103L
_node_alloc_traits_type::destroy(_node_allocator,__ptr);
_node_alloc_traits_type::deallocate(_node_allocator,__ptr,1);
#else
_node_allocator.destroy(__ptr);
_node_allocator.deallocate(__ptr,1);
#endif
}
template<typename _Tp,typename _Cmp,typename _Alloc>
typename treap<_Tp,_Cmp,_Alloc>::Node*
treap<_Tp,_Cmp,_Alloc>::merge(Node *lef_tree,Node *rig_tree)
{
if(lef_tree==nullptr)return rig_tree;
if(rig_tree==nullptr)return lef_tree;
if(lef_tree->pri>rig_tree->pri)
{
lef_tree->rc=merge(lef_tree->rc,rig_tree);
lef_tree->maintain();
return lef_tree;
}
else
{
rig_tree->lc=merge(lef_tree,rig_tree->lc);
rig_tree->maintain();
return rig_tree;
}
}
template<typename _Tp,typename _Cmp,typename _Alloc>
void
treap<_Tp,_Cmp,_Alloc>::split_val(Node *subtree_root,const _Tp &val,Node *&lef_tree,Node *&rig_tree)
{
if(subtree_root==nullptr)
{
lef_tree=nullptr;
rig_tree=nullptr;
return;
}
if(_Cmp::operator()(subtree_root->value,val))
{
lef_tree=subtree_root;
split_val(lef_tree->rc,val,lef_tree->rc,rig_tree);
}
else
{
rig_tree=subtree_root;
split_val(rig_tree->lc,val,lef_tree,rig_tree->lc);
}
subtree_root->maintain();
}
template<typename _Tp,typename _Cmp,typename _Alloc>
void
treap<_Tp,_Cmp,_Alloc>::split_val_equal(Node *subtree_root,const _Tp &val,Node *&lef_tree,Node *&rig_tree)
{
if(subtree_root==nullptr)
{
lef_tree=nullptr;
rig_tree=nullptr;
return;
}
if(!_Cmp::operator()(val,subtree_root->value))
{
lef_tree=subtree_root;
split_val_equal(lef_tree->rc,val,lef_tree->rc,rig_tree);
}
else
{
rig_tree=subtree_root;
split_val_equal(rig_tree->lc,val,lef_tree,rig_tree->lc);
}
subtree_root->maintain();
}
template<typename _Tp,typename _Cmp,typename _Alloc>
struct treap<_Tp,_Cmp,_Alloc>::iterator
{
private:
Node *ptr;
public:
iterator(){}
iterator(Node *ptr):
ptr(ptr)
{}
iterator(const iterator& Iter):
ptr(Iter.ptr)
{}
_Tp operator*()const
{
return ptr->value;
}
iterator &operator++()
{
if(ptr->rc!=nullptr)
{
ptr=ptr->rc;
while(ptr->lc!=nullptr)ptr=ptr->lc;
return *this;
}
else if(ptr->ftr!=nullptr)
{
while(ptr->ftr!=nullptr&&ptr==ptr->ftr->rc)ptr=ptr->ftr;
if(ptr->ftr!=nullptr&&ptr==ptr->ftr->lc)
{
ptr=ptr->ftr;
return *this;
}
}
}
iterator operator++(int)
{
Node *ptr0=ptr;
++*this;
return iterator(ptr0);
}
iterator &operator--()
{
if(ptr->lc!=nullptr)
{
ptr=ptr->lc;
while(ptr->rc!=nullptr)ptr=ptr->rc;
return *this;
}
else if(ptr->ftr!=nullptr)
{
while(ptr->ftr!=nullptr&&ptr==ptr->ftr->lc)ptr=ptr->ftr;
if(ptr->ftr!=nullptr&&ptr==ptr->ftr->rc)
{
ptr=ptr->ftr;
return *this;
}
}
}
iterator operator--(int)
{
Node *ptr0=ptr;
--*this;
return iterator(ptr0);
}
};
template<typename _Tp,typename _Cmp,typename _Alloc>
inline
unsigned long long
treap<_Tp,_Cmp,_Alloc>::get_pri()
{
#if __cplusplus>=201103L
static std::mt19937_64 rand_mker;
return rand_mker();
#else
return (rand()*1ULL<<32ULL)+rand();
#endif
}
template<typename _Tp,typename _Cmp,typename _Alloc>
void
treap<_Tp,_Cmp,_Alloc>::destroy_inner_nodes(Node *ptr)
{
if(ptr==nullptr)return;
destroy_inner_nodes(ptr->lc);
destroy_inner_nodes(ptr->rc);
__delete_node(ptr);
}
template<typename _Tp,typename _Cmp,typename _Alloc>
treap<_Tp,_Cmp,_Alloc>::~treap()
{
destroy_inner_nodes(end_node);
}
template<typename _Tp,typename _Cmp,typename _Alloc>
std::pair<typename treap<_Tp,_Cmp,_Alloc>::iterator,bool>
treap<_Tp,_Cmp,_Alloc>::insert(const _Tp& Value)
{
Node *ptr1,*ptr2,*ptr3;
split_val(root,Value,ptr1,ptr2);
split_val_equal(ptr2,Value,ptr2,ptr3);
if(ptr2!=nullptr)
{
root=merge(merge(ptr1,ptr2),ptr3);
return std::make_pair(iterator(end_node),false);
}
Node *new_ptr=__get_new_node(Value);
root=merge(merge(ptr1,new_ptr),ptr3);
return std::make_pair(iterator(new_ptr),true);
}
template<typename _Tp,typename _Cmp,typename _Alloc>
bool
treap<_Tp,_Cmp,_Alloc>::erase(const _Tp& Value)
{
Node *ptr1,*ptr2,*ptr3;
split_val(root,Value,ptr1,ptr2);
split_val_equal(ptr2,Value,ptr2,ptr3);
if(ptr2==nullptr)
{
root=merge(ptr1,ptr3);
return false;
}
root=merge(ptr1,ptr3);
__delete_node(ptr2);
return true;
}
template<typename _Tp,typename _Cmp,typename _Alloc>
typename treap<_Tp,_Cmp,_Alloc>::iterator
treap<_Tp,_Cmp,_Alloc>::begin()const
{
if(root==nullptr)return iterator(end_node);
Node *now=root;
while(now->lc!=nullptr)now=now->lc;
return iterator(now);
}
template<typename _Tp,typename _Cmp,typename _Alloc>
typename treap<_Tp,_Cmp,_Alloc>::iterator
treap<_Tp,_Cmp,_Alloc>::end()const
{
return iterator(end_node);
}
template<typename _Tp,typename _Cmp,typename _Alloc>
typename treap<_Tp,_Cmp,_Alloc>::iterator
treap<_Tp,_Cmp,_Alloc>::find(const _Tp& Value)const
{
Node *now=root;
while(now!=nullptr)
{
if(_Cmp::operator()(Value,now->value))now=now->lc;
else if(_Cmp::operator()(now->valueue,Value))now=now->rc;
else return iterator(now);
}
return iterator(end_node);
}
template<typename _Tp,typename _Cmp,typename _Alloc>
typename treap<_Tp,_Cmp,_Alloc>::iterator
treap<_Tp,_Cmp,_Alloc>::lower_bound(const _Tp& Value)const
{
Node *now=root,*ans=nullptr;
while(now!=nullptr)
{
if(!_Cmp::operator()(now->value,Value))
{
ans=now;
now=now->lc;
}
else
{
now=now->rc;
}
}
if(ans==nullptr)ans=end_node;
return iterator(ans);
}
template<typename _Tp,typename _Cmp,typename _Alloc>
typename treap<_Tp,_Cmp,_Alloc>::iterator
treap<_Tp,_Cmp,_Alloc>::upper_bound(const _Tp& Value)const
{
Node *now=root,*ans=nullptr;
while(now!=nullptr)
{
if(_Cmp::operator()(Value,now->value))
{
ans=now;
now=now->lc;
}
else
{
now=now->rc;
}
}
if(ans==nullptr)ans=end_node;
return iterator(ans);
}
template<typename _Tp,typename _Cmp,typename _Alloc>
typename treap<_Tp,_Cmp,_Alloc>::iterator
treap<_Tp,_Cmp,_Alloc>::find_by_order(const size_type& Order)const
{
size_type rest_order=Order;
Node *ans=root;
while(ans!=nullptr)
{
size_type ls=0;
if(ans->lc!=nullptr)ls=ans->lc->s;
if(ls>rest_order)
{
ans=ans->lc;
}
else if(ls<rest_order)
{
rest_order-=ls+1;
ans=ans->rc;
}
else return iterator(ans);
}
return iterator(ans);
}
template<typename _Tp,typename _Cmp,typename _Alloc>
typename treap<_Tp,_Cmp,_Alloc>::size_type
treap<_Tp,_Cmp,_Alloc>::order_of_key(const _Tp& Value)const
{
size_type ans=0;
Node *now=root;
while(now!=nullptr)
{
size_type ls=0;
if(now->lc!=nullptr)ls=now->lc->s;
if(_Cmp::operator()(now->value,Value))
{
ans+=ls+1;
now=now->rc;
}
else
{
now=now->lc;
}
}
return ans;
}
template<typename _Tp,typename _Cmp,typename _Alloc>
typename treap<_Tp,_Cmp,_Alloc>::size_type
treap<_Tp,_Cmp,_Alloc>::size()const
{
if(root==nullptr)return 0;
return root->size;
}
#if __cplusplus<201103L
#undef nullptr
#endif
#endif//Treap template
```
1. 为了提高运行速度，除了插入删除用分裂合并实现，各种查询都用迭代实现。
2. `_Tp`为元素类型，`_Cmp`为比较器，要求类似于`STL`，即比较器是一种满足严格弱序关系的二元谓词。
3. 使用该模板必须有`<functional>`库来提供默认的`std::less`，`<memory>`库来提供默认的`std::allocator`，其他随意
---
最后
$$whk\;for\;win,\;code\;for\;fun.$$