Splay模板 1.0
2024-08-27 16:31:15
struct Splay{
int rt,sz; ///根节点,树节点总数
int va[N],son[N][],fa[N];///值,左右儿子,父亲
void spin(int t){ ///旋转操作
int x=fa[t], f=fa[x], y=son[x][]==t;
son[x][y]=son[t][y^], fa[son[x][y]]=x;
son[t][y^]=x, fa[x]=t, fa[t]=f;
if(f) son[f][son[f][]==x]=t;
}
void play(int x){ /// splay操作
for(int i;i=fa[x];spin(x))
if(fa[i])
spin((x==son[i][])==(i==son[fa[i]][])?i:x);
rt=x;
}
void ins(int v){///插入元素
int y,x=rt;
while(){
y=son[x][va[x]<v];
if(!y){
y=++sz, va[y]=v, fa[y]=x;
son[y][]=son[y][]=;
son[x][va[x]<v]=y;
break;
}
x=y;
}play(y);
}
int suc(){ ///找后继
int x=rt,y=son[x][];
while(son[y][])y=son[y][];
return va[y];
}
int pre(){ ///找前驱
int x=rt,y=son[x][];
while(son[y][])y=son[y][];
return va[y];
}
void init(int x){ ///初始化,需要初始值
sz=rt=;va[rt]=x;
fa[]=son[][]=son[][]=;
}
}splay;
最新文章
- “安装项目” Step By Step
- [经验]Textbox 做日志记录,
- MBTI-性格测试
- tabbar底部标题和子控制器标题为什么会保持一致?
- 设计模式之美:Chain of Responsibility(职责链)
- ubuntu安装QQ目前最完善的方法!(亲测,成功)
- ASP.NET MVC 4应用程序文件夹
- 决策树及其python实现
- Swift自定义Class实现Hashable
- 用jQuery写了一个模态框插件
- Unity3D的SerializeField 序列化域名
- CNN详解
- Python处理json字符串转化为字典
- abp中文件下载,将内存数据导出到Excel并下载
- UI设计--->;全心全意为人民服务的宗旨---->;注重客户体验--->;软件持久的生命力
- 如何快速地开发一个微信小程序
- Apache 修改端口号
- (转)HIBERNATE与 MYBATIS的对比
- mfc CListCtrl
- 转载:C++中两个类中互相包含对方对象的指针问题