|
Treap完全体，有注释版本
#include<cstdio>
#include<vector>
#include<algorithm>
typedef long long ll;
using namespace std;
//head----------------------------
class Node//节点
{
public:
int lson;//左儿子
int rson;//右儿子
int val; //当前节点在堆中的优先级，为一个随机数
int key; //当前节点的键值
int size;//以当前节点为根的子树的大小（数的总量，相同的算多个）
int cnt; //当前节点 的 数的个数
};
//数组版Treap
class Treap
{
#define INF 2147483647
#define MAXN 2000000
#define ls(x) tr[x].lson
#define rs(x) tr[x].rson
#define NOT_FIND_RANK_BY_KEY 2147483647
#define NOT_FIND_KEY_BY_RANK 2147483647
#define NOT_FIND_PRE -2147483647
#define NOT_FIND_NXT 2147483647
#define NOT_FIND_MAX -2147483647
#define NOT_FIND_MIN 2147483647
#define INSERT_SUCCESS 1
#define INSERT_FAILED 0
#define REMOVE_SUCCESS 1
#define REMOVE_FAILED 0
#define NOT_FIND_KEY -1
public: //用户可以操作的函数
Treap(){build();} //构造函数
int getsize(); //集合中数的总数（重复的算多个）
int getmax(); //集合中的最大值
int getmin(); //集合中的最小值
bool insert(const int &key); //插入函数
bool remove(const int &key); //删除函数
int getpre(const int &key); //求前驱 集合中最大的 严格小于key的值
int getnxt(const int &key); //求后继 集合中最小的 严格大于key的值
int get_rank_by_key(const int &key); //查找 值为key的数 的排名
int get_key_by_rank(const int &rank);//查找 排名为rank的数
bool empty(); //查询 当前集合是否为空
int count(const int &key); //查询 数key在集合中出现的个数
void output(); //从小到大 输出集合中所有数
vector<int> preorder_traversal(); //当前平衡树 的 前序遍历
vector<int> inorder_traversal(); //当前平衡树 的 中序遍历
vector<int> post_order_traversal(); //当前平衡树 的 后序遍历
private: //Treap内部调用的函数，用户无法操作
Node tr[MAXN]; //所有节点，内存池
int idx; //当前已经使用了的内存池中 节点的编号
int root; //根节点的编号
void pushup(int u); //利用左右儿子信息更新当前节点信息 (向上更新)
void NewNode(int &u,const int &key); //创建一个键值为key的节点
void Lturn(int &u); //对编号为u的节点左旋
void Rturn(int &u); //对编号为u的节点右旋
void build(); //建树
bool insert(int &u,const int &key); //同public
bool remove(int &u,const int &key); //同public
int getpre(int u, const int &key); //同public
int getnxt(int u, const int &key); //同public
int get_rank_by_key(int u,int key); //同public
int get_key_by_rank(int u,int rank);//同public
int find(int u,const int &key); //查询键值为key的节点是否存在
void preorder_traversal (int u,vector<int> &ans); //同public
void inorder_traversal (int u,vector<int> &ans); //同public
void post_order_traversal(int u,vector<int> &ans); //同public
};
//private Treap内部调用的函数
/*pushup(int u)
参数 u : 当前节点编号
返回值：void
具体含义:利用儿子的信息更新自己的信息
以自己为根的子树大小，等于 左右儿子的大小 加上 自己存的数的个数
*/
inline void Treap::pushup( int u )
{
tr[u].size = tr[ls(u)].size + tr[rs(u)].size + tr[u].cnt;
}
/*NewNode(int &u,const int &key)
参数 u : 要新建的节点编号 变量的引用
key : 要新建的节点的键值
返回值: void
具体含义：创建键值为key的一个新的节点
先将内存池编号加一 并赋值给当前节点编号u
当前节点键值为给定键值
当前节点的优先级 随机分配一个 rand()
当前节点 大小和存的数的个数都是 1
*/
inline void Treap::NewNode( int &u , const int &key )
{
u = ++ idx;
tr[u].key = key;
tr[u].val = rand();
tr[u].size = 1;
tr[u].cnt = 1;
}
/*
Treap的核心操作 左旋右旋
左旋右旋实质为，
将u和v的父子关系对调，且使整棵树的中序遍历保持不变，
来维护 堆的性质（儿子的优先级比自己低）
作用：在完成某种操作后，倘若这棵树不满足堆的性质，
我们要在 不破坏这棵树的 中序遍历顺序 的 前提下 维护堆的性质
*/
/*
Rturn(int &u)
参数 u : 要旋转的节点编号的引用
返回值 : void
具体含义: 将当前节点进行右旋
左旋，将当前节点u和左儿子v右旋
u v
/ \ / \
v z -------> x u
/ \ / \
x y y z
上述过程中，x，z均没变(x还是v的左儿子,z还是u的右儿子)
y，u，v发生改变
u的左儿子变成了y（为旋转之前 v的右儿子） 对应代码中 tr[u].lson=tr[v].rson;
v的右儿子变成了u 对应代码中 tr[v].rson=u;
u和v交换位置了 对应代码中 u=v;
因为u，v发生了变化，且我们希望旋转后，我们所处的树中的位置不会变，所以u要重新到原来的位置
旋转之后，子树大小会发生改变，因此要自下而上 依次更新信息（pushup）
*/
inline void Treap::Rturn( int &u )
{
int v = tr[u].lson;
tr[u].lson = tr[v].rson;
tr[v].rson = u;
u = v;
pushup(rs(u));
pushup(u);
}
/*
Lturn(int &u)
左旋
和右旋同理 ，为右旋的逆过程
*/
inline void Treap::Lturn( int &u )
{
int v = tr[u].rson;
tr[u].rson = tr[v].lson;
tr[v].lson = u;
u = v;
pushup(ls(u));
pushup(u);
}
/*
build()
参数 void
返回值 : void
具体含义:建树
建立两个虚拟节点，分别为正无穷和负无穷，
以负无穷为根，根的右儿子是正无穷，
如果不满足堆的性质，就将右儿子左旋上来
*/
void Treap::build()
{
int u;
NewNode(root,-INF),NewNode(u,INF);
tr[root].rson = u;
if(tr[root].val < tr[u].val) Lturn(root);
pushup(root);
}
/*
insert(int &u,const int &key)
参数 u :当前走到的节点编号 的引用
key:要插入的键值
返回值 :是否插入成功，插入成功则返回INSERT_SUCCESS,插入失败返回INSERT_FAILED
具体含义:插入 key,当前已经走到节点 u
由于前面我们设立了两个虚拟节点2147483647 和-2147483647 当成正负无穷来用
因此以下所有的操作都不支持2147483648，-2147483647，-2147483648这三个数
如果当前节点为空：(u==0)
如果用到的内存池编号 已经接近内存池大小，就不能再插了
否则，直接插入当前节点并返回 true
如果当前节点非空：
如果当前节点的键值等于要插入的键值：
直接更新当前节点的cnt和size
否则，根据二叉搜索树（BST）的性质，插入到左（右）儿子上，
以插到左儿子上为例，当插入完成后，如果当前节点和左儿子不满足堆的性质，就把左儿子 右旋上来
插入到右儿子同理 。
*/
bool Treap::insert( int &u , const int &key )
{
if(key==INF || key==-INF || key==-INF-1)return INSERT_FAILED;
if(!u){
if(idx > MAXN-4)return INSERT_FAILED;
NewNode(u,key);
return INSERT_SUCCESS;
}
else if(tr[u].key == key){
tr[u].size++ , tr[u].cnt++;
return INSERT_SUCCESS;
}
else
{
if(tr[u].key > key)
{
insert(ls(u),key);
if(tr[u].val < tr[ls(u)].val)Rturn(u);
}
else
{
insert(rs(u),key);
if(tr[u].val < tr[rs(u)].val)Lturn(u);
}
pushup(u);
return INSERT_SUCCESS;
}
}
/*
remove(int &u,const int &key)
参数 u :当前走到的节点的编号的引用
key :要删除的键值
返回值 :是否删除成功，如果成功，返回REMOVE_SUCCESS,如果失败返回REMOVE_FAILED
具体含义 :删除一个元素key,当前已经走到节点 u
首先，规定两个虚拟节点不能被删除
如果 走到了一个空的节点，说明没有找到要删除的值，删除失败
如果当前节点的键值等于key:
如果当前节点的cnt大于1，直接减1即可
如果当前节点是叶节点（没有左右儿子）：直接删除
否则：
我们需要将当前节点 转到叶子上 进行删除
在往下转的时候，由于要维护堆的性质，
所以要把左右儿子中 优先级大的那个转上来（特别地，如果有一边为空，就把另一边转上来）
如果 右儿子为空 或者 左儿子优先级 大于 右儿子优先级
就右旋 ，并继续 递归右儿子，进行删除
否则 左旋， 搜索左儿子
最后由于，删完之后，子树大小发生改变，因此需要pushup
*/
bool Treap::remove( int &u , const int &key )
{
if(key == INF || key == -INF)return REMOVE_FAILED;
bool ok = false;
if(!u)return false;
else if(tr[u].key == key)
{
if(tr[u].cnt > 1)
{
tr[u].cnt--;
tr[u].size--;
return REMOVE_SUCCESS;
}
else if(tr[u].lson == 0 && tr[u].rson == 0)
{
u = 0;
return REMOVE_SUCCESS;
}
else
{
if(tr[u].rson == 0 || tr[ls(u)].val > tr[u].val)
{
Rturn(u);
ok = remove(rs(u),key);
}
else
{
Lturn(u);
ok = remove(ls(u),key);
}
}
}
else if(tr[u].key > key) ok = remove(ls(u),key);
else ok = remove(rs(u),key);
pushup(u);
return ok;
}
/*
getpre(int u,const int &key)
参数 u :当前走到的结点的编号
key :要查询的键值
返回值 :是否查询成功，查询成功返回对应键值，查询失败返回NOT_FIND_PRE
具体含义:寻找前驱，即小于key的最大数,当前已经走到节点u
如果当前节点为空，则没有找到前驱，寻找失败
如果当前节点的键值大于等于key，
那么键值为key的节点 如果存在，则只可能在左子树上，递归搜索左子树
如果当前节点的键值严格小于key，
那么键值为key的节点 如果存在，则只可能在右子树上，
且当前节点的键值，为 以当前节点为根的子树（除开右子树外）中所有键值的最大值，
因此当前节点可能就是答案，并搜索右子树，寻找答案，
两者取最大值
*/
int Treap::getpre( int u , const int &key )
{
if(u == 0)return NOT_FIND_PRE;
else if(tr[u].key >= key)return getpre(ls(u),key);
else return max( tr[u].key , getpre(rs(u),key));
}
/*
getnxt(int u,const int &key)
寻找后继，即大于key的最小数
同getpre
*/
int Treap::getnxt( int u , const int &key )
{
if(u == 0)return NOT_FIND_NXT;
else if(tr[u].key <= key)return getnxt(rs(u),key);
else return min(tr[u].key , getnxt(ls(u),key));
}
/*
get_rank_by_key(int u,int key)
参数 u : 当前走到的节点编号
key: 查询的键值
返回值 : 是否查询成功，查询成功返回对应的排名，查询失败返回 NOT_FIND_RANK_BY_KEY
具体含义：通过给定键值，寻找该键值 在以当前节点为根的子树 中的排名
（注意上述定义，排名定义于当前子树）
如果走到了一个空节点，则没有找到对应的键值
如果当前节点的键值就是要找的key，则排名为，左子树的大小加一
如果当前节点的键值大于key，则键值为key的节点如果存在，只可能在左子树中，递归查找左子树
如果当前节点的键值小于key，
键值为key的节点如果存在，只可能在右子树中,
因此，只需查询右子树中键值key的排名，
这个排名加上当前节点的cnt，再加上左子树的大小，
就是key在 以当前节点为根的子树中的排名
*/
int Treap::get_rank_by_key( int u , int key )
{
if(u == 0)return NOT_FIND_RANK_BY_KEY;
else if(tr[u].key == key)return tr[ls(u)].size + 1;
else if(tr[u].key > key) return get_rank_by_key(ls(u),key);
else
{
int ok = get_rank_by_key(rs(u),key);
if(ok == NOT_FIND_RANK_BY_KEY)return NOT_FIND_RANK_BY_KEY;
else return tr[ls(u)].size + tr[u].cnt+ok;
}
}
/*
get_key_by_rank(int u,int rank)
参数 u : 当前走到的节点编号
rank: 查询的排名
返回值 : 如果查询成功返回键值，查询失败返回NOT_FIND_KEY_BY_RANK
具体含义：寻找 以当前节点为根的子树中 排名为rank的键值
（注意定义，这个排名定义于当前子树下）
如果 走到了一个空节点，说明没有查找到符合要求的键值 ，查询失败
如果当前节点的左子树大小 大于等于 rank，则 key一定在左子树中，递归搜索左子树
如果rank 严格大于 左子树大小，且 小于等于左子树大小 加上 当前节点的cnt：
如果当前节点为虚拟节点，查询失败
否则当前节点就是答案，返回当前节点的key
如果rank严格大于左子树大小 加上 当前节点的cnt:
则要查询的key 为右子树中 排名为 rank减去左子树和当前节点大小 的 节点
*/
int Treap::get_key_by_rank( int u , int rank )
{
if(u == 0) return NOT_FIND_KEY_BY_RANK;
if(tr[ls(u)].size >= rank)return get_key_by_rank(ls(u),rank);
else if(( tr[u].key == INF || tr[u].key == -INF) && rank <= tr[ls(u)].size + tr[u].cnt)
return NOT_FIND_KEY_BY_RANK;
else if(rank <= tr[ls(u)].size + tr[u].cnt )return tr[u].key;
else return get_key_by_rank(rs(u),rank - tr[u].cnt - tr[ls(u)].size);
}
/*
find (int u,const int &key)
参数 u : 当前走到的节点编号
key: 查询的键值
返回值 : 查询成功返回编号，否则返回NOT_FIND_KEY
具体含义：查询当前节点为根的子树中，键值为key的节点是否存在
如果走到了一个空节点，查询失败
如果当前节点的key 为所查询的key ，直接返回当前节点的编号
否则 根据 BST 的性质 递归查询左（右）子树
*/
int Treap::find( int u , const int &key )
{
if(u == 0)return NOT_FIND_KEY;
if(tr[u].key == key)return u;
else if(tr[u].key < key)return find(rs(u),key);
else return find(ls(u),key);
}
/*
getsize ()
参数 无
返回值 :返回元素个数
具体含义：查询整棵树中元素的个数
*/
int Treap::getsize()
{
return tr[root].size - 2;
}
/*
getmax()
参数 无
返回值 ：如果查询成功返回最大值，否则返回NOT_FIND_MAX
具体含义：查询最大值
最大值即为比正无穷小的最大值，即无穷大的前驱
如果无穷大的前驱 为负无穷，则最大值不存在
否则 直接返回结果
*/
int Treap::getmax()
{
int ok = getpre(root,INF);
if(ok == -INF)return NOT_FIND_MAX;
else return ok;
}
/*
getmin()
同getmax
*/
int Treap::getmin()
{
int ok = getnxt(root,-INF);
if(ok == INF)return NOT_FIND_MIN;
else return ok;
}
/*
preorder_traversal(int u,vector<int> &ans)
参数 u : 当前走到的节点编号
ans: 当前遍历到的所有节点所构成的序列 的引用
返回值 : void
具体含义：前序遍历
如果当前节点为空，则直接停止搜索
根据前序遍历的定义，
先搜索左子树，
再搜索当前节点（如果不是虚拟节点，就加入答案）
再搜索右子树
*/
void Treap::preorder_traversal( int u , vector<int> &ans )
{
if(u == 0)return ;
preorder_traversal(ls(u),ans);
if(tr[u].key != INF && tr[u].key != -INF)
for(int i = 1 ; i <= tr[u].cnt ; i++) ans.push_back(tr[u].key);
preorder_traversal(rs(u),ans);
}
/*
inorder_traversal(int u,vector<int> &ans)
参数 u : 当前走到的节点编号
ans: 当前遍历到的所有节点所构成的序列 的引用
返回值 : void
具体含义：中序遍历
如果当前节点为空，则直接停止搜索
根据中序遍历的定义，
先搜索当前节点（如果不是虚拟节点，就加入答案）
再搜索左子树，
再搜索右子树
*/
void Treap::inorder_traversal( int u , vector<int> &ans )
{
if(u == 0)return ;
if(tr[u].key != INF && tr[u].key != -INF)
for(int i = 1;i <= tr[u].cnt;i++)ans.push_back(tr[u].key);
preorder_traversal(ls(u),ans);
preorder_traversal(rs(u),ans);
}
/*
post_order_traversal(int u,vector<int> &ans)
参数 u : 当前走到的节点编号
ans: 当前遍历到的所有节点所构成的序列 的引用
返回值 : void
具体含义：后序遍历
如果当前节点为空，则直接停止搜索
根据后序遍历的定义，
先搜索左子树，
再搜索右子树
再搜索当前节点（如果不是虚拟节点，就加入答案）
*/
void Treap::post_order_traversal( int u , vector<int> &ans )
{
if(u == 0)return ;
preorder_traversal(ls(u),ans);
preorder_traversal(rs(u),ans);
if(tr[u].key != INF&&tr[u].key != -INF)
for(int i = 1;i <= tr[u].cnt;i ++)ans.push_back(tr[u].key);
}
// public 用户可以调用的函数
/*
insert(const int &key)
参数 key : 插入的键值
返回值 : 插入成功返回INSERT_SUCCESS,否则返回INSERT_FAILED
具体含义：插入元素key
*/
bool Treap::insert( const int &key )
{
return insert(root,key);
}
/*
remove(const int &key)
参数 key : 删除的键值
返回值 : 删除成功返回REMOVE_SUCCESS,否则返回REMOVE_FAILED
具体含义：移除一个元素key
*/
bool Treap::remove( const int &key )
{
return remove(root,key);
}
/*
getpre(const int &key)
参数 key : 查询的键值
返回值 : 查询成功返回前驱,否则返回NOT_FIND_PRE
具体含义：求key的前驱
*/
int Treap::getpre( const int &key )
{
return getpre(root,key);
}
/*
getnxt(const int &key)
参数 key : 查询的键值
返回值 : 查询成功返回后继,否则返回NOT_FIND_NXT
具体含义：求key的后继
*/
int Treap::getnxt( const int &key )
{
return getnxt(root,key);
}
/*
get_rank_by_key(const int &key)
参数 key : 查询的键值
返回值 : 查询成功返回排名,否则返回NOT_FIND_RANK_BY_KEY
具体含义：查询元素key的排名
因为有虚拟节点，所以真实排名为查询到的排名减1
*/
int Treap::get_rank_by_key( const int &key )
{
int ok = get_rank_by_key(root,key);
if(ok == NOT_FIND_RANK_BY_KEY)return NOT_FIND_RANK_BY_KEY;
else return ok - 1;
}
/*
get_key_by_rank(const int &rank)
参数 rank : 查询的排名
返回值 : 查询成功返回键值,否则返回NOT_FIND_KEY_BY_RANK
具体含义：查询排名为rank的数
由于有虚拟节点，因此传进去的时候要将排名+1
*/
int Treap::get_key_by_rank( const int &rank )
{
int ok = get_key_by_rank(root,rank+1);
if(ok == NOT_FIND_KEY_BY_RANK)return NOT_FIND_KEY_BY_RANK;
else return ok;
}
/*
empty()
参数 : void
返回值 : 如果为集合空返回true，否则返回false
具体含义：判断集合是否为空
*/
bool Treap::empty()
{
return tr[root].size == 2;
}
/*
count (const int &key)
参数 key : 查询的键值
返回值 : 返回键值出现的次数
具体含义：查询元素key出现了多少次
*/
int Treap::count( const int &key )
{
int ok = find(root,key);
if(ok == NOT_FIND_KEY)return 0;
else return tr[ok].cnt;
}
/*
output()
参数 : void
返回值 : void
具体含义：从小到大依次输出所有元素
*/
void Treap::output()
{
vector<int> ans = preorder_traversal();
for(auto p:ans)printf("%d ",p);
}
/*
preorder_traversal ()
参数 : void
返回值 : 返回前序遍历序列，存在vector中
具体含义：前序遍历
*/
vector<int> Treap::preorder_traversal()
{
vector<int> ans;
preorder_traversal(root,ans);
return ans;
}
/*
inorder_traversal ()
参数 : void
返回值 : 返回中序遍历序列，存在vector中
具体含义：中序遍历
*/
vector<int> Treap::inorder_traversal()
{
vector<int> ans;
inorder_traversal(root,ans);
return ans;
}
/*
post_order_traversal()
参数 : void
返回值 : 返回后序遍历序列，存在vector中
具体含义：后序遍历
*/
vector<int> Treap::post_order_traversal()
{
vector<int> ans;
post_order_traversal(root,ans);
return ans;
}
#undef ls
#undef rs
#undef MAXN
#undef INF
Treap treap;
//test
void test();//内部调试
void test2();//用户使用
int main()
{
//
// freopen("data.in","r",stdin);
// freopen("33.out","w",stdout);
test2();
test();
}
void show_menu()//菜单
{
puts("请输入两个整数 t 和 x ( 输入格式为 t x )");
puts(" 0 退出请输入 0 和 一个任意数");
puts(" 1 查询当前集合大小请输入 1 和 一个任意数");
puts(" 2 查询当前集合最大值请输入 2 和 一个任意数");
puts(" 3 查询当前集合最小值请输入 3 和 一个任意数");
puts(" 4 插入一个数x 请输入 4 和 x");
puts(" 5 删除一个数x 请输入 5 和 x");
puts(" 6 查询比x小的最大数请输入 6 和 x");
puts(" 7 查询比x大的最小数请输入 7 和 x");
puts(" 8 查询值为x的数的排名请输入 8 和 x");
puts(" 9 查询大小排名为x的数请输入 9 和 x");
puts(" 10 查询集合是否为空请输入 10 和 一个任意数");
puts(" 11 查询一个数x出现多少次请输入 11 和 x");
puts(" 12 将所有数从小到大输出请输入 12 和 x");
puts(" 13 输出这棵树的前序遍历请输入 13 和 一个任意数");
puts(" 14 输出这棵树的前序遍历请输入 14 和 一个任意数");
puts(" 15 输出这棵树的前序遍历请输入 15 和 一个任意数");
}
void test2()
{
for(int ii=1;;ii++)
{
show_menu();
int op,x,id=ii;
scanf("%d%d",&op,&x);
printf("id=%-3d op=%-3d x=%-3d \n",id,op,x);
printf("-------------------------");
printf("----------------------------------------\n您的查询(操作)结果为 ");
if(op==0)break;
if(op==1)
{
printf("%d",treap.getsize());
}
else if(op==2)
{
int ok=treap.getmax();
if(ok==NOT_FIND_MAX)printf("not find max");
else printf("%d",ok);
}
else if(op==3)
{
int ok=treap.getmin();
if(ok==NOT_FIND_MIN)printf("not find min");
else printf("%d",ok);
}
else if(op==4)
{
treap.insert(x);//insert失败功能暂不测试
printf("insert success");
}
else if(op==5)
{
int ok=treap.remove(x);
if(ok==REMOVE_FAILED)printf("remove failed");
else printf("remove success");
}
else if(op==6)
{
int ok=treap.getpre(x);
if(ok==NOT_FIND_PRE)printf("not find pre");
else printf("%d",ok);
}
else if(op==7)
{
int ok=treap.getnxt(x);
if(ok==NOT_FIND_NXT)printf("not find nxt");
else printf("%d",ok);
}
else if(op==8)
{
int ok=treap.get_rank_by_key(x);
if(ok==NOT_FIND_RANK_BY_KEY)printf("not find rank by key");
else printf("%d",ok);
}
else if(op==9)
{
int ok=treap.get_key_by_rank(x);
if(ok==NOT_FIND_KEY_BY_RANK)printf("not find key by rank");
else printf("%d",ok);
}
else if(op==10)
{
int ok=treap.empty();
printf(ok?"empty":"not empty");
}
else if(op==11)
{
printf("%d",treap.count(x));
}
else if(op==12)
{
treap.output();
}
else if(op==13)
{
vector<int> ans=treap.preorder_traversal();
for(auto p:ans)printf("%d ",p);
}
else if(op==14)
{
vector<int> ans=treap.inorder_traversal();
for(auto p:ans)printf("%d ",p);
}
else if(op==15)
{
vector<int> ans=treap.post_order_traversal();
for(auto p:ans)printf("%d ",p);
}
puts("");
printf("-----------------------------------------------------------------\n\n");
}
}
void test()
{
int n;scanf("%d",&n);
for(int iii=1;iii<=n;iii++)
{
int op,x,id;
scanf("%d%d%d",&id,&op,&x);
printf("id=%-3d op=%-3d x=%-3d ",id,op,x);
if(op==1)
{
printf("%d",treap.getsize());
}
else if(op==2)
{
int ok=treap.getmax();
if(ok==NOT_FIND_MAX)printf("not find max");
else printf("%d",ok);
}
else if(op==3)
{
int ok=treap.getmin();
if(ok==NOT_FIND_MIN)printf("not find min");
else printf("%d",ok);
}
else if(op==4)
{
treap.insert(x);//insert失败功能暂不测试
}
else if(op==5)
{
int ok=treap.remove(x);
if(ok==REMOVE_FAILED)printf("remove failed");
}
else if(op==6)
{
int ok=treap.getpre(x);
if(ok==NOT_FIND_PRE)printf("not find pre");
else printf("%d",ok);
}
else if(op==7)
{
int ok=treap.getnxt(x);
if(ok==NOT_FIND_NXT)printf("not find nxt");
else printf("%d",ok);
}
else if(op==8)
{
int ok=treap.get_rank_by_key(x);
if(ok==NOT_FIND_RANK_BY_KEY)printf("not find rank by key");
else printf("%d",ok);
}
else if(op==9)
{
int ok=treap.get_key_by_rank(x);
if(ok==NOT_FIND_KEY_BY_RANK)printf("not find key by rank");
else printf("%d",ok);
}
else if(op==10)
{
int ok=treap.empty();
printf(ok?"empty":"not empty");
}
else if(op==11)
{
printf("%d",treap.count(x));
}
else if(op==12)
{
treap.output();
}
else if(op==13)
{
vector<int> ans=treap.preorder_traversal();
for(auto p:ans)printf("%d ",p);
}
else if(op==14)
{
vector<int> ans=treap.inorder_traversal();
for(auto p:ans)printf("%d ",p);
}
else if(op==15)
{
vector<int> ans=treap.post_order_traversal();
for(auto p:ans)printf("%d ",p);
}
puts("");
}
}
简单版本（Acwing253.普通平衡树）
#include<cstdio>
#include<algorithm>
#include<ctime>
using namespace std;
const int N=1e5+500;
const int INF=2e9;
#define ls(x) tr[x].ls
#define rs(x) tr[x].rs
struct Node
{
int ls,rs;
int key,val;
int size,cnt;
}tr[N];
int idx,root;
int getNode(int key)
{
++idx;
tr[idx].key=key;
tr[idx].val=rand();
tr[idx].cnt=tr[idx].size=1;
return idx;
}
void pushup(int u)
{
tr[u].size=tr[ls(u)].size+tr[rs(u)].size+tr[u].cnt;
}
void zig(int &p)//右旋 p为根，q为p的左儿子
{
int q=ls(p);
tr[p].ls=tr[q].rs;
tr[q].rs=p;
p=q;
pushup(tr[p].rs);
pushup(p);
}
void zag(int &p)
{
int q=rs(p);
tr[p].rs=tr[q].ls;
tr[q].ls=p;
p=q;
pushup(tr[p].ls);
pushup(p);
}
void build()
{
getNode(-INF),getNode(INF);
root=1,tr[1].rs=2;
if(tr[1].val<tr[2].val)zag(root);
pushup(root);
}
void insert(int &p,int key)
{
if(!p)p=getNode(key);
else if(tr[p].key==key) tr[p].cnt++;
else if(tr[p].key>key)
{
insert(tr[p].ls,key);
if(tr[ls(p)].val>tr[p].val)zig(p);
}
else
{
insert(tr[p].rs,key);
if(tr[rs(p)].val>tr[p].val)zag(p);
}
pushup(p);
}
void remove(int &p,int key)
{
if(!p)return ;
if(tr[p].key==key)
{
if(tr[p].cnt>1)tr[p].cnt--;
else if(tr[p].ls==0&&tr[p].rs==0) p=0;//叶节点，直接删
else
{
if(!tr[p].rs||tr[ls(p)].val>tr[rs(p)].val)
{
zig(p);
remove(rs(p),key);
}
else
{
zag(p);
remove(ls(p),key);
}
}
}
else if(tr[p].key>key)remove(ls(p),key);
else remove(rs(p),key);
pushup(p);
}
int getpre(int p,int key)//严格比这个数小的数
{
if(!p)return -INF;
if(tr[p].key>=key)return getpre(ls(p),key);
else return max(tr[p].key,getpre(rs(p),key));
}
int getnxt(int p,int key)
{
if(!p)return INF;
if(tr[p].key<=key)return getnxt(rs(p),key);
else return min(tr[p].key,getnxt(ls(p),key));
}
int get_rank_by_key(int p,int key)
{
if(!p)return -1; // key不存在
if(tr[p].key==key)return tr[ls(p)].size+1;
else if(tr[p].key>key)
{
return get_rank_by_key(ls(p),key);
}
else return tr[ls(p)].size+tr[p].cnt+get_rank_by_key(rs(p),key);
}
int get_key_by_rank(int p,int rank)
{
if(!p)return INF; //排名为rank的数不存在
if(tr[ls(p)].size>=rank)return get_key_by_rank(ls(p),rank);
else if(rank<=tr[ls(p)].size+tr[p].cnt)return tr[p].key;
else return get_key_by_rank(rs(p),rank-tr[p].cnt-tr[ls(p)].size);
}
int main()
{
build();
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
int t,x;
scanf("%d%d",&t,&x);
if(t==1)
{
insert(root,x);
}
if(t==2)
{
remove(root,x);
}
if(t==3)
{
printf("%d\n",get_rank_by_key(root,x)-1);
}
if(t==4)
{
printf("%d\n",get_key_by_rank(root,x+1));
}
if(t==5)
{
printf("%d\n",getpre(root,x));
}
if(t==6)
{
printf("%d\n",getnxt(root,x));
}
}
}
|