P5076 【深基16.例7】普通二叉树（简化版）
题目描述
您需要写一种数据结构，来维护一些数（都是绝对值 $10^9$ 以内的数）的集合，最开始时集合是空的。其中需要提供以下操作，操作次数 $q$ 不超过 $10^4$：
- 定义数 $x$ 的排名为集合中小于 $x$ 的数的个数 $+1$。查询数 $x$ 的排名。注意 $x$ 不一定在集合里。
- 查询排名为 $x(x\ge 1)$ 的数。保证集合里至少有 $x$ 个数。
- 求 $x$ 的前驱（前驱定义为小于 $x$，且最大的数）。若不存在则输出 $-2147483647$。
- 求 $x$ 的后继（后继定义为大于 $x$，且最小的数）。若不存在则输出 $2147483647$。
- 插入一个数 $x$，本题的数据保证插入前 $x$ 不在集合中。
保证执行 $1,3,4$ 操作时，集合中有至少一个元素。
输入格式
第一行是一个整数 $q$，表示操作次数。
接下来 $q$ 行，每行两个整数 $op,x$，分别表示操作序号以及操作的参数 $x$。
输出格式
输出有若干行。对于操作 $1,2,3,4$，输出一个整数，表示该操作的结果。
输入输出样例 #1
输入 #1
1
2
3
4
5
6
7
8
| 7
5 1
5 3
5 5
1 3
2 2
3 3
4 3
|
输出 #1
题解
方法1
使用BST
一个实现如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
| #include<bits/stdc++.h>
using namespace std;
using i64=long long;
using u64=unsigned long long;
using u32=unsigned;
using u128=unsigned __int128;
const int inf=2147483647;
struct node{
int v;
int lchild=0,rchild=0;
int siz;
}bst[100010];
int cnt=0;
void insert(int v,int idx){
bst[idx].siz++;
if(v>bst[idx].v){
if(bst[idx].rchild!=0){
insert(v,bst[idx].rchild);
}
else{
cnt++;
bst[cnt].v=v;
bst[cnt].siz=1;
bst[idx].rchild=cnt;
}
}
else{
if(bst[idx].lchild!=0){
insert(v,bst[idx].lchild);
}
else{
cnt++;
bst[cnt].v=v;
bst[cnt].siz=1;
bst[idx].lchild=cnt;
}
}
}
int findPre(int v){
int idx=1;
int ans=-inf;
while(idx){
if(bst[idx].v<v){
ans=bst[idx].v;
idx=bst[idx].rchild;
}
else{
idx=bst[idx].lchild;
}
}
return ans;
}
int findPost(int v){
int idx=1;
int ans=inf;
while(idx){
if(bst[idx].v>v){
ans=bst[idx].v;
idx=bst[idx].lchild;
}
else{
idx=bst[idx].rchild;
}
}
return ans;
}
int fromRankfindV(int rk,int idx){
int leftSize=bst[bst[idx].lchild].siz;
if(rk<=leftSize){
return fromRankfindV(rk,bst[idx].lchild);
}
else if(rk==leftSize+1){
return bst[idx].v;
}
else{
return fromRankfindV(rk-leftSize-1,bst[idx].rchild);
}
}
int fromVfindRank(int v,int idx){
if(idx==0) return 0;
if(v<=bst[idx].v){
return fromVfindRank(v,bst[idx].lchild);
}
else{
return bst[bst[idx].lchild].siz+1+fromVfindRank(v,bst[idx].rchild);
}
}
int main(){
ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
int q;
cin>>q;
while(q--){
int op;
int x;
cin>>op>>x;
if(op==1){
cout<<fromVfindRank(x,1)+1<<"\n";
}
else if(op==2){
cout<<fromRankfindV(x,1)<<"\n";
}
else if(op==3){
cout<<findPre(x)<<"\n";
}
else if(op==4){
cout<<findPost(x)<<"\n";
}
else if(op==5){
if(cnt==0){
cnt=1;
bst[1].v=x;
bst[1].siz=1;
}
else insert(x,1);
}
}
return 0;
}
|
但是找前驱和找后继的函数可以省略，因为可以先查询x的排名rank，然后查询排名为rank-1和rank+1的数，就分别是前驱和后继了。
如果rank+1>cnt或者rank-1<1，那么就可以分别输入inf和-inf
方法2
使用STL容器multiset
multiset的常见用法详解
multiset的定义
multiset 是一个集合容器，它可以存储多个相同的元素。换句话说，如果你有一堆重复的数，比如 3、5、5、5、7，你可以用multiset来妥善管理它们。与set不同的是，set不会允许重复的元素，而multiset非常欢迎重复元素的加入。
可以使用统一初始化的元素来创建
1
2
3
4
5
6
7
8
9
10
| int main() {
multiset<int> numbers = {3, 5, 5, 7, 3, 9};
for (int num : numbers) {
cout << num << " ";
}
return 0;
}
|
注意，multiset会自动按升序排列元素。
如果是自定义类型，需要重载小于号
multiset内元素的访问
使用迭代器
multiset常用函数实例解析
insert()
略了
erase()
erase方法用来删除元素。但是要注意！如果你直接传入一个值，所有与这个值相同的元素都会被删除。如果你只想删除一个特定的元素，最好先找到它的迭代器，然后用这个迭代器来删除。
1
2
3
4
5
6
7
8
9
10
11
12
13
| int main() {
multiset<int> numbers = {3, 5, 5, 7};
numbers.erase(5);
for (int num : numbers) {
cout << num << " ";
}
return 0;
}
|
如果只想删除第一个5
1
2
3
4
| auto it = numbers.find(5);
if (it != numbers.end()) {
numbers.erase(it);
}
|
size()
略了
clear()
略了
empty()
略
lower_bound()
略 和algorithm中的不一样
upper_bound()
略 和algorithm中的不一样
分析题目
1. 查询 x 数的排名
排名，说白了就是排序之后的x的下标。
我们只要用lower_bound方法，找到第一个x的位置。
然后从begin开始往后遍历容器，只要达到这个位置，就输出当前下标即可。
2.查询排名为 x 的数
遍历容器，只要当前排名到达x，就输出当前值。
（因为multiset容器无法进行随机访问）
3.求 x 的前驱（前驱定义为小于 x，且最大的数）
前驱，也就是x的前一个。
我们只要用lower_bound方法找到第一个x的位置，然后输出上一个就OK了。
4.求 x 的后继（后继定义为大于 x，且最小的数）。
后继，也就是第一个大于x的数。
我们可以用upper_bound方法，直接找到这个值。
5.插入一个数 x
直接用insert方法插入即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
| #include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<set>
using namespace std;
multiset<int>q;
int n,t,x,order;
int main()
{
q.insert(-0x7fffffff);
q.insert(0x7fffffff);
scanf("%d",&n);
while(n--)
{
scanf("%d%d",&t,&x);
if(t==1)
{
auto it=q.lower_bound(x);
order=0;
for(auto i=q.begin();i!=it;i++,order++);
printf("%d\n",order);
}
else if(t==2)
{
order=-1;
for(int i:q)
if(++order==x)
printf("%d\n",i);
}
else if(t==3)
{
auto it=q.lower_bound(x);
printf("%d\n",*--it);
}
else if(t==4)
{
printf("%d\n",*q.upper_bound(x));
}
else
{
q.insert(x);
}
}
return 0;
}
|