生活随笔
收集整理的这篇文章主要介绍了
AcWing 253. 普通平衡树
小编觉得挺不错的,现在分享给大家,帮大家做个参考.
您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：
插入数值x。删除数值x(若有多个相同的数，应只删除一个)。查询数值x的排名(若有多个相同的数，应输出最小的排名)。查询排名为x的数值。求数值x的前驱(前驱定义为小于x的最大的数)。求数值x的后继(后继定义为大于x的最小的数)。
注意： 数据保证查询的结果一定存在。
本题为平衡树基本操作的代码实现
using namespace std
;const int N
= 100010, INF
= 1e8
;int n
;
struct Node
{int l, r
;int key, val
;int cnt, size
;
}tr
[N
];int root, idx
;void pushup
(int p
)
{tr
[p
].size
= tr
[tr
[p
].l
].size + tr
[tr
[p
].r
].size + tr
[p
].cnt
;
}int get_node
(int key
)
{tr
[ ++ idx
].key
= key
;tr
[idx
].val
= rand
();tr
[idx
].cnt
= tr
[idx
].size
= 1;return idx
;
}void zig
(int
&p
) // 右旋
{int q
= tr
[p
].l
;tr
[p
].l
= tr
[q
].r, tr
[q
].r
= p, p
= q
;pushup
(tr
[p
].r
), pushup
(p
);
}void zag
(int
&p
) // 左旋
{int q
= tr
[p
].r
;tr
[p
].r
= tr
[q
].l, tr
[q
].l
= p, p
= q
;pushup
(tr
[p
].l
), pushup
(p
);
}void
build()
{get_node
(-INF
), get_node
(INF
);root
= 1, tr
[1].r
= 2;pushup
(root
);if (tr
[1].val
< tr
[2].val
) zag
(root
);
}void insert
(int
&p, int key
)
{if (!p
) p
= get_node
(key
);else if (tr
[p
].key
== key
) tr
[p
].cnt ++
;else if (tr
[p
].key
> key
){insert
(tr
[p
].l, key
);if (tr
[tr
[p
].l
].val
> tr
[p
].val
) zig
(p
);}else{insert
(tr
[p
].r, key
);if (tr
[tr
[p
].r
].val
> tr
[p
].val
) zag
(p
);}pushup
(p
);
}void remove
(int
&p, int key
)
{if (!p
) return;if (tr
[p
].key
== key
){if (tr
[p
].cnt
> 1) tr
[p
].cnt --
;else if (tr
[p
].l
|| tr
[p
].r
){if (!tr
[p
].r
|| tr
[tr
[p
].l
].val
> tr
[tr
[p
].r
].val
){zig
(p
);remove
(tr
[p
].r, key
);}else{zag
(p
);remove
(tr
[p
].l, key
);}}else p
= 0;}else if (tr
[p
].key
> key
) remove
(tr
[p
].l, key
);else remove
(tr
[p
].r, key
);pushup
(p
);
}int get_rank_by_key
(int p, int key
) // 通过数值找排名
{if (!p
) return 0; // 本题中不会发生此情况
if (tr
[p
].key
== key
) return tr
[tr
[p
].l
].size +
1;if (tr
[p
].key
> key
) return get_rank_by_key
(tr
[p
].l, key
);return tr
[tr
[p
].l
].size + tr
[p
].cnt + get_rank_by_key
(tr
[p
].r, key
);
}int get_key_by_rank
(int p, int rank
) // 通过排名找数值
{if (!p
) return INF
; // 本题中不会发生此情况
if (tr
[tr
[p
].l
].size
>= rank
) return get_key_by_rank
(tr
[p
].l, rank
);if (tr
[tr
[p
].l
].size + tr
[p
].cnt
>= rank
) return tr
[p
].key
;return get_key_by_rank
(tr
[p
].r, rank - tr
[tr
[p
].l
].size - tr
[p
].cnt
);
}int get_prev
(int p, int key
) // 找到严格小于key的最大数
{if (!p
) return -INF
;if (tr
[p
].key
>= key
) return get_prev
(tr
[p
].l, key
);return max
(tr
[p
].key, get_prev
(tr
[p
].r, key
));
}int get_next
(int p, int key
) // 找到严格大于key的最小数
{if (!p
) return INF
;if (tr
[p
].key
<= key
) return get_next
(tr
[p
].r, key
);return min
(tr
[p
].key, get_next
(tr
[p
].l, key
));
}int
main()
{build
();scanf
("%d",
&n
);while (n --
){int opt, x
;scanf
("%d%d",
&opt,
&x
);if (opt
== 1) insert
(root, x
);else if (opt
== 2) remove
(root, x
);else if (opt
== 3) printf
("%d\n", get_rank_by_key
(root, x
) -
1);else if (opt
== 4) printf
("%d\n", get_key_by_rank
(root, x +
1));else if (opt
== 5) printf
("%d\n", get_prev
(root, x
));else printf
("%d\n", get_next
(root, x
));}return 0;
}
Vector版偷懒平衡树
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std
;
vector
<int>v
;
int n
,opt
,x
;
int main()
{v
.reserve(100001);scanf("%d",&n
);while(n
--){scanf("%d%d",&opt
,&x
);if(opt
==1) v
.insert(lower_bound(v
.begin(),v
.end(),x
),x
);if(opt
==2) v
.erase (lower_bound(v
.begin(),v
.end(),x
));if(opt
==3) printf("%d\n",lower_bound(v
.begin(),v
.end(),x
)-v
.begin()+1);if(opt
==4) printf("%d\n",v
[x
-1]);if(opt
==5) printf("%d\n",v
[lower_bound(v
.begin(),v
.end(),x
)-v
.begin()-1]);if(opt
==6) printf("%d\n",v
[upper_bound(v
.begin(),v
.end(),x
)-v
.begin()]);}return 0;
}
总结
以上是生活随笔为你收集整理的AcWing 253. 普通平衡树的全部内容，希望文章能够帮你解决所遇到的问题。
如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。
