洛谷P2286 HNOI2004-《宠物收养场》 Treap树
发布时间
阅读量：
阅读量
treap树
本题关键点：
1、构建两棵treap树，其中一棵用于存储宠物信息，另一棵则用于存储顾客数据。题目中明确指出，所有顾客值与宠物值均互不相同。
为此，Treap结构体只需额外增加一个size字段，用于记录子树中节点的总数。
2、依据treap树的模板进行代码实现，完成以下相关函数的编写。由于涉及两棵树的操作，因此在函数参数传递过程中需要使用引用方式。
int New(int val, Treap* a, int& tot)
void update(int p, Treap* a)
void Build(Treap* a, int& tot, int& root)
void zig(int &p, Treap* a) //右旋转
void zag(int &p, Treap* a) //左旋
void Insert(int &p, int val, Treap* a, int& tot)
int GetPre(int val, Treap* a, int root)
int GetNext(int val, Treap* a, int root)
void Remove(int &p, int val, Treap* a)
全部评论 (0)
还没有任何评论哟~