Splay 板子
发布日期:2021-09-25 23:57:59 浏览次数:15 分类:技术文章

本文共 2978 字,大约阅读时间需要 9 分钟。

BST是个好东西,不过在成一条链的时候就会退化成 O(n) ,所以Splay诞生了~

Splay可以改善这种情况,没事就Splay一下,就有可能把链变成别的结构,反正就很神奇。
下面是洛谷第一个题解的模板,虽然有点问题,但是稍微修改一下就可以过了~

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define X first#define Y second#define L (u<<1)#define R (u<<1|1)#define Mid (tr[u].l+tr[u].r>>1)#define Len(u) (tr[u].r-tr[u].l+1)#define pb push_back#define mk make_pairusing namespace std;typedef long long LL;typedef pair
PII;const int N=100010,mod=1e9+7,INF=0x3f3f3f3f;const double eps=1e-6;struct Splay{ #define root e[0].ch[1]//e[0] 代表超级根,右孩子即为树根 struct node { int v,father;//v是结点值,father是父亲结点 int ch[2];//ch[0] 左节点 ch[1] 右结点 int sum;//包含自己下面有多少元素(非结点) int recy;//该结点元素出现次数(非结点) }; node e[N]; int n,points;//n代表已经用的编号 void update(int x)//更新当前结点sum { e[x].sum=e[e[x].ch[0]].sum+e[e[x].ch[1]].sum+e[x].recy; } int identify(int x)//确定当前结点是父亲的左孩子还是右孩子 { return e[e[x].father].ch[0]==x? 0:1; } void connect(int x,int f,int son)//x作为f的son(左右)儿子 { e[x].father=f; e[f].ch[son]=x; } void rotate(int x)//旋转节点 { int y=e[x].father; int mroot=e[y].father; int mrootson=identify(y); int yson=identify(x); int B=e[x].ch[yson^1]; connect(B,y,yson); connect(y,x,(yson^1)); connect(x,mroot,mrootson); update(y); update(x); } void splay(int at,int to)//伸展操作 { to=e[to].father; while(e[at].father!=to) { int up=e[at].father; if(e[up].father==to) rotate(at);//只需要旋一次 else if(identify(up)==identify(at)) { //三点共线 rotate(up); rotate(at); } else { //不共线 rotate(at); rotate(at); } } } int crepoint(int v,int father)//添加节点 { n++; e[n].v=v; e[n].father=father; e[n].sum=e[n].recy=1; return n; } void destory(int x)//摧毁节点 { e[x].v=e[x].ch[0]=e[x].ch[1]=e[x].sum=e[x].father=e[x].recy=0; if(x==n) n--;//优化 } int find(int v)//查找结点 { int now=root; while(1) { if(e[now].v==v) { splay(now,root); return now; } int next= v
1) { e[deal].recy--; e[deal].sum--; return; } if(!e[deal].ch[0]) { root=e[deal].ch[1]; e[root].father=0; } else { int lef=e[deal].ch[0]; while(e[lef].ch[1]) lef=e[lef].ch[1]; splay(lef,e[deal].ch[0]); int rig=e[deal].ch[1]; connect(rig,lef,1); connect(lef,0,1); update(lef); } destory(deal); } int rank(int v)//获取元素的排名 { int ans=0,now=root; while(1) { if(e[now].v==v) { ans+=e[e[now].ch[0]].sum; splay(now,root); return ans+1; } if(now==0) return 0; if(v
points) return -INF; int now=root; while(1) { int minused=e[now].sum-e[e[now].ch[1]].sum; if(x>e[e[now].ch[0]].sum&&x<=minused) break; if(x
v&&e[now].v
v 等号看情况 if(v
result) result=e[now].v;//e[now].v
e[now].v) now=e[now].ch[1]; else now=e[now].ch[0]; } return result; } #undef root}S;int main(){ // ios::sync_with_stdio(false);// cin.tie(0); int n; scanf("%d",&n); while(n--) { int op,x; scanf("%d%d",&op,&x); if(op==1) S.push(x); else if(op==2) S.pop(x); else if(op==3) printf("%d\n",S.rank(x)); else if(op==4) printf("%d\n",S.atrank(x)); else if(op==5) printf("%d\n",S.lower(x)); else if(op==6) printf("%d\n",S.upper(x)); } return 0;}/**/

转载地址:https://blog.csdn.net/DaNIelLAk/article/details/108263958 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:左偏树(可并堆)
下一篇:Reverse and Swap CodeForces - 1401 F 线段树 + 思维

发表评论

最新留言

第一次来,支持一个
[***.219.124.196]2024年03月14日 18时19分11秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

hadoop 3.3 一直停留在running wordcount_蛋价持续下跌,今日跌破3.3元大关!深秋季节价格还能反弹吗?... 2019-04-21
的流程图做完后如何保存_2019超火的半永久眉是哪款?做完后我们如何护理?... 2019-04-21
去除logo 高德地图api_深圳品牌logo升级如何保持原型的同时更具创新? 2019-04-21
二重积分转换成极坐标_二重积分转换极坐标r的范围如何确定? 2019-04-21
python中倒背如流_八字基础知识--倒背如流篇 2019-04-21
以太坊地址和公钥_以太坊地址是什么 2019-04-21
linux查看wifi信号命令_linux – 获取WIFI信号强度 – 寻求最佳方式(IOCTL,iwlist(iw)等)... 2019-04-21
npm 不重启 全局安装后_解决修复npm安装全局模块权限的问题 2019-04-21
vs格式化json 不生效_vs code 格式化 json 配置 2019-04-21
go 字符串反序列化成对象数组_Fastjson 1.2.24反序列化漏洞深度分析 2019-04-21
onmessage websocket 收不到信息_WebSocket断开重连解决方案,心跳重连实践 2019-04-21
hibernate mysql 缓存_hibernate和mysql的缓存问题,没辙了! 2019-04-21
abp框架 mysql_ABP框架使用Mysql数据库 2019-04-21
mysql树形递归删除_使用递归删除树形结构的所有子节点(java和mysql实现) 2019-04-21
linux mysql 不能连接远程_linux mysql 远程连接 2019-04-21
mysql $lt_mongodb中比较级查询条件:($lt $lte $gt $gte)(大于、小于)、查找条件... 2019-04-21
install python_Install python on AIX 7 2019-04-21
jquery查找div下第一个input_jquery查找div元素第一个元素id 2019-04-21
如何修改手机屏幕显示的长宽比例_屏幕分辨率 尺寸 比例 长宽 如何计算 2019-04-21
mysql 的版本 命名规则_MySQL版本和命名规则 2019-04-21