云计算百科
云计算领域专业知识百科平台

洛谷 P3369:[模板] 普通平衡树 ← Splay树

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */
#content_views .toc,
/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */
#content_views.markdown_views > p:empty:has(+ .toc),
#content_views.markdown_views > .toc + p:empty,
/* 富文本旧版目录标记 */
#content_views.htmledit_views #main-toc,
#content_views.htmledit_views #hr-toc,
#content_views.htmledit_views p[id*=\”-toc\”] {
display: none !important;
}
/* 目录去掉后,紧跟的首个标题不再多出一块上边距 */
#content_views.markdown_views > .toc + h1,
#content_views.markdown_views > .toc + h2,
#content_views.markdown_views > .toc + h3,
#content_views.markdown_views > .toc + h4,
#content_views.markdown_views > .toc + p:empty + h1,
#content_views.markdown_views > .toc + p:empty + h2,
#content_views.markdown_views > .toc + p:empty + h3,
#content_views.markdown_views > .toc + p:empty + h4 {
margin-top: 0 !important;
}

【题目来源】 https://www.luogu.com.cn/problem/P3369 【题目描述】 您需要动态地维护一个可重集合 M,并且提供以下操作: (1)向 M 中插入一个数 x。 (2)从 M 中删除一个数 x。(若有多个相同的数,应只删除一个) (3)查询 M 中有多少个数比 x 小,并且将得到的答案加 1。 (4)查询如果将 M 从小到大排列后,排名位于第 x 位的数。 (5)查询 M 中 x 的前驱(定义为 M 中小于 x,且最大的数)。 (6)查询 M 中 x 的后继(定义为 M 中大于 x,且最小的数)。 对于操作 3,5,6,不保证当前可重集中存在数 x。 对于操作 4,5,6,保证答案一定存在。 【输入格式】 第一行为 n,表示操作的个数,下面 n 行每行有两个数 opt 和 x,opt 表示操作的序号(1≤opt≤6)。​​​​​​​ 【输出格式】 对于操作 3,4,5,6 每行输出一个数,表示对应答案。​​​​​​​ 【输入样例】 10 1 106465 4 1 1 317721 1 460929 1 644985 1 84185 1 89851 6 81968 1 492737 5 493598​​​​​​​ 【输出样例】 106465 84185 492737​​​​​​​ 【数据范围】 对于 100% 的数据,1≤n≤10^5,∣x∣≤10^7。 【算法分析】 ● Treap 树解决平衡的办法是给每个结点加上一个随机的优先级,实现概率上的平衡。Splay 树直接用旋转调整树的形态,通过旋转改善树的平衡性。计算量小,效果好。 ● Splay 树的旋转主要分为“单旋”和“双旋”。 所谓“单旋”,即把结点 x 与它的父结点交换位置,使结点 x 上升一层。“单旋”不会减少树的层数,对改善平衡性没有帮助。根据旋转方向,“单旋”又分为左旋(zag)与右旋(zig)。 所谓“双旋”,即两次“单旋”。“双旋”同时旋转结点 x,父结点 f 及祖父结点 g 等3个结点,能改善平衡性。“双旋”又分为“一字旋”与“之字旋”。 ● Splay 树的旋转示意图

● Splay 树的基本操作是把结点旋转到树的根部,这样下次访问它时,只需查一次就 OK 了。 ● Splay 树是动态树(LCT,Link Cut Tree)与树链剖分的基础。 ● Splay 树曾经是最常使用的 BST。不过,现在经常使用 FHQ Treap 树实现很多传统的 Splay 树的题目。因为,FHQ Treap 树代码更容易写,效率也很高,且可做持久化。 【算法代码】

#include <bits/stdc++.h>
using namespace std;

const int maxn=2e6+5;
const int inf=0x3f3f3f3f;
int root,idx;

struct Node {
int ch[2],val,fa;
int size,cnt;
} tr[maxn];

void pushup(int x) {
tr[x].size=tr[tr[x].ch[0]].size+tr[tr[x].ch[1]].size+tr[x].cnt;
}

void rotate(int x) {
int y=tr[x].fa;
int z=tr[y].fa;
int k=(tr[y].ch[1]==x);
int b=tr[x].ch[k^1];

if(z) tr[z].ch[tr[z].ch[1]==y]=x;
tr[x].fa=z;
tr[y].ch[k]=b;
if(b) tr[b].fa=y;
tr[x].ch[k^1]=y;
tr[y].fa=x;

pushup(y);
pushup(x);
}

void splay(int x,int k) {
while(tr[x].fa!=k) {
int y=tr[x].fa;
int z=tr[y].fa;
if(z!=k) {
if((tr[y].ch[0]==x)^(tr[z].ch[0]==y)) rotate(x);
else rotate(y);
}
rotate(x);
}
if(!k) root=x;
}

void insert(int x) {
int u=root,p=0;
while(u && tr[u].val!=x) {
p=u;
u=tr[u].ch[x>tr[u].val];
}
if(u) {
tr[u].cnt++;
pushup(u);
} else {
u=++idx;
if(p) tr[p].ch[x>tr[p].val]=u;
tr[u].ch[0]=tr[u].ch[1]=0;
tr[u].fa=p;
tr[u].val=x;
tr[u].size=tr[u].cnt=1;
}
splay(u,0);
}

int get_pri_by_val(int x) {
int u=root,p=0,res=0;
while(u) {
p=u;
if(tr[u].val<x) {
res+=tr[tr[u].ch[0]].size+tr[u].cnt;
u=tr[u].ch[1];
} else {
u=tr[u].ch[0];
}
}
if(p) splay(p,0);
return res;
}

int get_val_by_pri(int k) {
int u=root;
while(true) {
int ls=tr[tr[u].ch[0]].size;
if(k<=ls) u=tr[u].ch[0];
else if(k<=ls+tr[u].cnt) break;
else k-=ls+tr[u].cnt, u=tr[u].ch[1];
}
splay(u,0);
return tr[u].val;
}

int get_pre(int x) {
int u=root,p=0;
while(u) {
if(tr[u].val<x) {
p=u;
u=tr[u].ch[1];
} else u=tr[u].ch[0];
}
if(p) splay(p,0);
return p;
}

int get_suc(int x) {
int u=root,p=0;
while(u) {
if(tr[u].val>x) {
p=u;
u=tr[u].ch[0];
} else u=tr[u].ch[1];
}
if(p) splay(p,0);
return p;
}

void remove(int x) {
int pre=get_pre(x),suc=get_suc(x);
splay(pre,0);
splay(suc,pre);
int del=tr[suc].ch[0];
if(!del || tr[del].val!=x) return;
if(tr[del].cnt>1) {
tr[del].cnt–;
pushup(del),pushup(suc),pushup(pre);
} else {
tr[suc].ch[0]=0;
pushup(suc),pushup(pre);
}
}

int main() {
ios::sync_with_stdio(0);
cin.tie(0);

insert(-inf);
insert(inf);

int T;
cin>>T;
while(T–) {
int op,x;
cin>>op>>x;
if(op==1) insert(x);
else if(op==2) remove(x);
else if(op==3) cout<<get_pri_by_val(x)<<endl;
else if(op==4) cout<<get_val_by_pri(x+1)<<endl;
else if(op==5) {
int pos=get_pre(x);
if(pos) cout<<tr[pos].val<<endl;
} else if(op==6) {
int pos=get_suc(x);
if(pos) cout<<tr[pos].val<<endl;
}
}
return 0;
}

/*
in:
10
1 106465
4 1
1 317721
1 460929
1 644985
1 84185
1 89851
6 81968
1 492737
5 493598

out:
106465
84185
492737
*/

【参考文献】 https://blog.csdn.net/hnjzsyjyj/article/details/138541955 https://blog.csdn.net/hnjzsyjyj/article/details/138522947 https://blog.csdn.net/hnjzsyjyj/article/details/138504578  

赞(0)
未经允许不得转载:网硕互联帮助中心 » 洛谷 P3369:[模板] 普通平衡树 ← Splay树
分享到: 更多 (0)

评论 抢沙发

评论前必须登录!