当前位置: 首页 > news >正文

有旋Treap

#include<iostream>using namespace std;
/*本代码模拟的是小根堆*/
const int N = 5e5+1, INF = 0x3f3f3f3f;
struct node {int l, r, val, pos, siz, cnt;
//val:结点的值,pos:随机生成的优先级(尽量避免退化成单链),siz:以该点为根节点的子树大小,cnt:与val值相同的节点个数(搜索二叉树不允许有两个值相同的节点)
};
node tree[N];
int cnt, root; //编号、根节点
int n;void zig(int &x) { //右旋(为左子节点的右节点);实质:在满足二叉搜索树的性质的基础上比较优先级int y = tree[x].l;tree[x].l = tree[y].r;//左子节点的右节点变为父节点x的左子节点(不明白画个图)tree[y].r = x;//左子节点的右节点变为父节点tree[y].siz = tree[x].siz;//左子节点继承子树节点数量tree[x].siz = tree[tree[x].l].siz + tree[tree[x].r].siz + tree[x].cnt;//更新x = y;//替代(为什么形参里传得是地址)
}
void zag(int &x) { //左旋(为右子节点的左子节点)int y = tree[x].r;//同上tree[x].r = tree[y].l;tree[y].l = x;tree[y].siz = tree[x].siz;tree[x].siz = tree[tree[x].l].siz + tree[tree[x].r].siz + tree[x].cnt;x = y;
}
void insert(int &x, int key) {//插入新节点if (!x) {//当前节点不存在x = ++cnt;tree[x].val = key;tree[x].pos = rand();tree[x].l = tree[x].r = 0;tree[x].cnt = tree[x].siz = 1;return ;}++tree[x].siz;//子树节点数量加一if (key == tree[x].val) {++tree[x].cnt;//相同值的数量加一return ;}if (key < tree[x].val) {//二叉搜索树的性质(下同)insert(tree[x].l, key);if (tree[x].pos > tree[tree[x].l].pos)zig(x);return ;}if (key > tree[x].val) {insert(tree[x].r, key);if (tree[x].pos > tree[tree[x].r].pos)zag(x);return ;}
}
void del(int &x, int key) {//删除值为key的旧节点if (tree[x].val == key) {//当前结点的值恰好为key,所以接下来就不必进行if (tree[x].cnt > 1) {//存在多个--tree[x].cnt;--tree[x].siz;return;}if (!tree[x].l || !tree[x].r)//没有子节点或类似于一条单链x = tree[x].l + tree[x].r;//相当于用子节点直接替代或变为叶子节点else {if (tree[tree[x].l].pos < tree[tree[x].r].pos){//因为x将要被删除(所以讨论儿子),所以为了保证满足堆的性质,所以要先使用左旋或右旋,在删除//模拟的是小根堆(根节点优先级小于子节点)zig(x);del(x, key);}else{zag(x);del(x, key);}}return;}--tree[x].siz;if (key < tree[x].val)//二叉搜索树的性质del(tree[x].l, key);elsedel(tree[x].r, key);
}
int getpre(int key) {//得到前驱(比key小的最大值)int x = root, pre = -INF;//pr:找到的上一个前驱while (x) {//直至找到叶子节点if (tree[x].val < key)//既然当前节点的值比key小,满足前提条件,说明我们要去它的右子树去寻找尽可能大的值(BST二叉搜索树的性质)pre = tree[x].val, x = tree[x].r;else//如果连前提条件都不满足,即当前节点的值不小于key,那么就要去左子树里去找了x = tree[x].l;}return pre;//返回值
}
int getnex(int key) {//得到后继(比key大的最小值)(类似于前驱)int x = root, nex = INF;while (x) {if (tree[x].val > key)nex = tree[x].val, x = tree[x].l;elsex = tree[x].r;}return nex;
}
int queryval(int k) {//查询排名所对应的值int x = root;while (x) {if (k > tree[tree[x].l].siz && k <= tree[tree[x].l].siz + tree[x].cnt)//排名在子树范围内return tree[x].val;if (k <= tree[tree[x].l].siz)//小于范围,找左子树x = tree[x].l;else {//大于范围,找右子树//通常来说,根节点与左子树被看作是一体的,与右子树区分开,//例如ls=1,2,3 x=5 rs=6,7,那么3在树和子树中都是第三个,而6在树中是第5名,在右子树中是第1名k -= tree[tree[x].l].siz + tree[x].cnt;x = tree[x].r;}}return 0;
}
int queryrank(int key) {//查询值所对应的排名int x = root, res = 0;while (x) {if (key == tree[x].val)//刚好相等return res + tree[tree[x].l].siz + 1;//从左子树的范围转移过来if (key < tree[x].val)//小于值(根据性质,去找左子树)x = tree[x].l;else {//大于值(根据性质,去找右子树)res += tree[tree[x].l].siz + tree[x].cnt;x = tree[x].r;}}return res;
}int main() {ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);cin >> n;int op, x;for (int i = 1; i <= n; ++i) {cin >> op >> x;switch (op) {case 1:insert(root, x);break;case 2:del(root, x);break;case 3:cout << queryrank(x) << '\n';break;case 4:cout << queryval(x) << '\n';break;case 5:cout << getpre(x) << '\n';break;case 6:cout << getnex(x) << '\n';break;}}return 0;
}
http://www.hskmm.com/?act=detail&tid=20256

相关文章:

  • xxO
  • 情绪识别论文阅读——Eyemotion - 详解
  • 2025年山东设备回收公司TOP交易服务推荐排行榜,济宁,梁山设备回收,二手,饮料,食品,制药,实验室,生产线,化工厂,废旧,大型,专业设备回收公司推荐
  • 做了个TIFF图片格式转换工具,感觉怎么样?
  • C#后遗症,掉了个坑,特此记录
  • 曾记否 -- Words to be remembered 2025.9.28
  • 日常掉坑记录: 关于位操作
  • WPF XAML资源文件中的换行、回车、空格及Tab的转义
  • longchain4j 学习系列(2)-调用远程deepseek
  • 收汇核销简介
  • macOS 彻底卸载和重装 Node.js 指南
  • 题解:CF2023F Hills and Pits
  • 2025最新国内过滤器品牌 TOP10 权威测评推荐厂家与选购指南
  • Python 将 HTML 转换为纯文本 TXT (HTML 文本提取) - 实践
  • 0135_MVC 设计模式:让代码架构更清晰
  • 30天Python编程挑战 - 从零基础到全栈开发
  • 软件工程第一次作业——物品复活系统
  • StatusStrip 状态栏控件的使用
  • 2025过滤器厂家最新推荐TOP5排行榜:覆盖环保过滤器、精密过滤器、高效过滤器,帮企业找到适配优质厂商
  • 9.28
  • ubi文件系统的 制作 + 挂载
  • 一款开源免费、组件丰富的 WPF UI 控件库,提供了 100 多款常用控件!
  • 元推理用无限嵌套,取代目前弱ai的暴力无限试错
  • 解题报告-序列(alis.*)
  • Cloudbox工具箱!一款拥有100款工具的超级工具箱!Cloudbox工具箱教程(附下载)
  • java 语法基础课后作业
  • Lightroom使用教程!一文学会Lightroom使用教程!软件攻略(批量处理)
  • C++篇 String实现避坑指南:搞定构造,拷贝与析构,增删查改,流提取流插入与比对大小 一文全解 - 教程
  • AT_agc026_c [AGC026C] String Coloring
  • 启发式合并 [PA 2014] Fiolki