bzoj3224: Tyvj 1728 普通平衡树(打个splay暖暖手)
发布日期:2021-08-10 02:43:35 浏览次数:1 分类:技术文章

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

  (其实今天好热啊?

  题目大意:插入,删除,k小,前驱后继,数的排名。

  splay和treap裸题...过几天补个treap的

splay:

#include
#include
#include
#include
#define which(x) (son[fa[x]][1]==x)using namespace std;const int extar[2]={
2147483647,-2147483647};int fa[100010],count[100010],son[100010][3],val[100010],data[100010];int root,x,y,n,tot,xiugai;void read(int &k){ k=0;int f=1;char c=getchar(); while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); while(c<='9'&&c>='0')k=k*10+c-'0',c=getchar(); k*=f;}void rotate(int x){ int f=fa[x]; bool k=which(x); son[f][k]=son[x][!k];son[x][!k]=f;son[fa[f]][which(f)]=x; if(son[f][k])fa[son[f][k]]=f;fa[x]=fa[f];fa[f]=x; count[x]=count[f]; count[f]=count[son[f][0]]+count[son[f][1]]+val[f];}void splay(int x,int g){ while(fa[x]!=g) { int f=fa[x]; if(fa[f]==g) { rotate(x); break; } if(which(x)^which(f))rotate(x); else rotate(f); rotate(x); } if(!g)root=x;}int search(int x,int y){ if(data[x]>y&&son[x][0])return search(son[x][0],y); if(data[x]
x)return data[k]; return ext(son[k][1],1);}int rank(int x,int k){ if(k<=count[son[x][0]])return rank(son[x][0],k); if(k<=(count[son[x][0]]+val[x]))return x; return rank(son[x][1],k-count[son[x][0]]-val[x]);}int findnum(int x){ int k=search(root,x); splay(k,0); return count[son[k][0]]+1;}void insert(int &x,int w,int f){ if(!x) { x=++tot; count[x]=val[x]=1; data[x]=w; fa[x]=f; xiugai=tot; return; } if(data[x]==w)val[x]++,xiugai=x; if(data[x]
w)insert(son[x][0],w,x); count[x]++;}void del(int w){ int k=search(root,w); splay(k,0); if(data[k]==w) { if(val[k]>1)val[k]--,count[k]--; else if(!son[k][0]) { root=son[k][1]; fa[root]=fa[k]=son[k][1]=count[k]=val[k]=data[k]=0; } else { fa[son[k][0]]=0;ext(son[k][0],0); son[root][1]=son[k][1]; if(son[k][1])fa[son[k][1]]=root; count[root]+=count[son[k][1]]; fa[k]=son[k][0]=son[k][1]=data[k]=val[k]=count[k]=0; } }}int main(){ read(n); for(int i=1;i<=n;i++) { read(x);read(y); switch(x) { case 1:insert(root,y,0);splay(xiugai,0);root=xiugai;break; case 2:del(y);break; case 3:printf("%d\n",findnum(y));break; case 4:printf("%d\n",data[rank(root,y)]);break; case 5:printf("%d\n",pred(y));break; case 6:printf("%d\n",succ(y));break; default:break; } }}
View Code

 

转载于:https://www.cnblogs.com/Sakits/p/6838764.html

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

上一篇:proxy模式
下一篇:P1865 A % B Problem 素数筛

发表评论

最新留言

逛到本站,mark一下
[***.202.152.39]2024年02月29日 03时16分10秒

关于作者

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

推荐文章

owdcloud mysql_MySQL在Ubuntu远程配置 2019-04-21
python基础装饰器_Python基础 装饰器及练习 2019-04-21
python导出csv不带引号的句子_不带双引号写入CSV文件 2019-04-21
python爬虫代码模板_Python:学习Python爬虫的第一天 2019-04-21
springboot获取原生js请求_springboot跳转原生html 2019-04-21
java buffer nio_Java NIO之Buffer(缓冲区)入门 2019-04-21
android java加密_android 和java平台通用的AES加密解密 2019-04-21
java导出类_java导出excel工具类 2019-04-21
java学习手册下载_Java学习手册 2019-04-21
axios delete有请求体吗_关于axios请求——delete方法 2019-04-21
java 自助更改密码 api_搭建ldap自助修改密码系统--Self Service Password 2019-04-21
php继承exten,stylus中文文档 » 继承(@extend) » 张鑫旭-鑫空间-鑫生活 2019-04-21
mysql函数大全 pdf,MySQL函数大全 2019-04-21
php 常用文件系统函数,php 文件系统函数整理介绍 2019-04-21
android pm.java,java – AM / PM的Android DateFormat因设备而异 2019-04-21
oracle存储过程调用sql文件,oracle - 在SQL Developer中运行存储过程? 2019-04-21
oracle同时报604和12507,V$SES_OPTIMIZER_ENV 查不到刚修改的隐含参数, 2019-04-21
zblog的php更换域名,zblogphp更换域名后,原zblog里使用了固定域名,登录不进去怎么办... 2019-04-21
oracle dnfs 配置,Source of Oracle参数解析(dnfs_batch_size) - django-\/\/ i K | 2019-04-21
oracle所需的环境,转:面对一个全新的oracle环境,首先应该了解什么? 2019-04-21