首页 > 代码库 > 【整合】SBT模板(全部操作)
【整合】SBT模板(全部操作)
插入,删除,前驱后继,第k大值,排名,最大值最小值8种询问外带核心左旋右旋Maintain
全套模板整合
从16:10开始写,写到了16:28
总计用时18min左右(前后误差不超过1min)
我的手速还真是快呢owo
这一次就是个小测试了。看来到现在SBT已经写熟练了0-0
可以去颓Splay和fhqTreap之类的了www
P.S.应该没写错吧。。。有什么写错了的有人看出来了马上告诉我QUQ
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; struct sbt { int left,right,size,data; }tree[100000]; int top,root; int n; int opt; int key; void left_rot(int &x) { int y=tree[x].right; tree[x].right=tree[y].left; tree[y].left=x; tree[y].size=tree[x].size; tree[x].size=tree[tree[x].left].size+tree[tree[x].right].size+1; x=y; } void right_rot(int &x) { int y=tree[x].left; tree[x].left=tree[y].right; tree[y].right=x; tree[y].size=tree[x].size; tree[x].size=tree[tree[x].left].size+tree[tree[x].right].size+1; x=y; } void Maintain(int &x,bool flag) { if (!flag) { if (tree[tree[tree[x].left].left].size>tree[tree[x].right].size) right_rot(x); else if (tree[tree[tree[x].left].right].size>tree[tree[x].right].size) left_rot(tree[x].left),right_rot(x); else return; } else { if (tree[tree[tree[x].right].right].size>tree[tree[x].left].size) left_rot(x); else if (tree[tree[tree[x].right].left].size>tree[tree[x].left].size) right_rot(tree[x].right),left_rot(x); else return; } Maintain(tree[x].left,0); Maintain(tree[x].right,1); Maintain(x,1); Maintain(x,0); } void insert(int &x,int data) { if (x==0) { x=++top; tree[x].size=1; tree[x].left=tree[x].right=0; tree[x].data=http://www.mamicode.com/data;>【整合】SBT模板(全部操作)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。