p3369 [模板]普通平衡树[Treap]

题目描述

您需要写一种数据结构(可参考题目标题),来维护一些数,其中需要提供以下操作:

  1. 插入x数
  2. 删除x数(若有多个相同的数,因只删除一个)
  3. 查询x数的排名(若有多个相同的数,因输出最小的排名)
  4. 查询排名为x的数
  5. 求x的前驱(前驱定义为小于x,且最大的数)
  6. 求x的后继(后继定义为大于x,且最小的数)

    输入输出格式

    输入格式:

    第一行为n,表示操作的个数,下面n行每行有两个数opt和x,opt表示操作的序号(1<=opt<=6)

    输出格式:

    对于操作3,4,5,6每行输出一个数,表示对应答案

    输入输出样例

    输入样例#1:

    10
    1 106465
    4 1
    1 317721
    1 460929
    1 644985
    1 84185
    1 89851
    6 81968
    1 492737
    5 493598

    输出样例#1:

    106465
    84185
    492737

    说明

    时空限制:1000ms,128M
    1.n的数据范围:n<=100000
    2.每个数的数据范围:[-1e7,1e7]
    来源:Tyvj1728 原名:普通平衡树
    在此鸣谢

    题解

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
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct node
{
node* ch[2];
int w;
int v;
int s;//节点数
int flag;//由于某种原因,所以~
node()
{
ch[0]=NULL;
ch[1]=NULL;
w=rand();
v=0;
s=1;
flag=1;
}
};
node* root;
inline void maintain(node* &u)//更新该节点所对的树的节点总数
{
u->s=u->flag;//flag存的是权值为v的点的个数
if (u->ch[0]!=NULL) u->s+=u->ch[0]->s;//左子树不为空就加上左子树的节点数
if (u->ch[1]!=NULL) u->s+=u->ch[1]->s;//右子树不为空就加上右子树的节点数
}
inline void turn(node* &u,int d)//左旋右旋,d=0:左旋,1:右旋
{//我们假设为左旋
node* k=u->ch[d^1];//提出u的右子树,u的右子数的根节点作为整个树的根节点
u->ch[d^1]=k->ch[d];//右子树的左节点,作根节点的右节点
k->ch[d]=u;//原本的树u,作k树的左子树
maintain(u);//更新u之后k才能更新
maintain(k);//更新k
u=k;//赋过去
}
inline void insert(node* &u,int d)
{
if (u==NULL)//如果u为空直接插进去
{
u=new node;
u->v=d;
return;
} else
if (u->v==d)//因为可能有相同的,所以统flag,然后更新
{
u->flag++;
maintain(u);
return;
}
int d1=d>u->v?1:0;//判断是应该搜左子树还是右子树
insert(u->ch[d1],d);
if (u->ch[d1]->w > u->w) turn(u,d1^1); //看搜的子树的权重,比较,旋转
else maintain(u); //旋转过程中已经更了节点数,没旋也要更新
}
inline void remove(node* &u,int d)
{
if (u==NULL) return;//空的就退掉
if (u->v==d)
{
if (u->flag>1) u->flag--;//如果这个值出现多次直接减
else
{
if (u->ch[0]==NULL&&u->ch[1]==NULL)
{//没左子树和右子树直接删除
u=NULL;
} else
if (u->ch[0]!=NULL&&u->ch[1]!=NULL)
{//有两个子树就看哪边权重大,然后旋过去,然后继续搜那个子树
if (u->ch[0]->w >u->ch[1]->w) turn (u,1),remove(u->ch[1],d); else turn(u,0),remove(u->ch[0],d);
} else
{//只有一个子树就直接拿另一个棵子树补上
if (u->ch[0]==NULL) u=u->ch[1]; else u=u->ch[0];
}
}
if (u!=NULL) maintain(u);//不为空才统计
} else
{//根据d的大小扫左子树和右子树
if (d < u->v) remove(u->ch[0],d); else
if (d > u->v) remove(u->ch[1],d);
if (u!=NULL) maintain(u);//更新
}
}
inline int sum(node* u,int k)//查询排名为k的数
{
if (k<0||k>u->s||u==NULL) return 0; //不合法的情况直接退出
int ss=0;//ss:u的左子树的节点个数,没有则为0,省得分类讨论
if (u->ch[0]!=NULL) ss=u->ch[0]->s;//更新
if (k>=ss+1&&k<=u->flag+ss) return u->v;//嗯因为u有flag个,所以在ss+1~ss+flag这个范围就算找到了
if (ss>=k) return sum(u->ch[0],k); //ss大了就往左子树扫
else return sum(u->ch[1],k-ss-u->flag);//否则就搜右子树
}
inline int ans(node* u,int k)//查询k的排名
{
if (u==NULL) return 0;//不合法的情况
int ss=0;//存左子树的节点数,不然没左子树就要再分
if (u->ch[0]!=NULL) ss=u->ch[0]->s;
if (u->v==k) return ss+1;//返回排名最小的,所以是ss+1
if (u->v>k) //大了搜左边
{
return ans(u->ch[0],k);
}
else//搜右子输的时候要把左子树的节点数加上
{
return ss+u->flag+ans(u->ch[1],k);
}
}
inline void qq(node* u,int k,int &ans)//求k的前驱
{
if (u==NULL) return;
if (u->v<k)
{
if (u->v > ans) ans=u->v;//日常更新,没有往左扫的必要了
if (u->ch[1]!=NULL) qq(u->ch[1],k,ans);//所以右子树不为空就扫
} else
if (u->v>=k)//大了的话就往左扫,仅此而已
{
if (u->ch[0]!=NULL) qq(u->ch[0],k,ans);
} //左子树不为空就往左扫
}
inline void hj(node* u,int k,int &ans)//求k的后继
{
if (u==NULL) return;
if (u->v>k)//其实原理和前驱差不多
{
if (u->v < ans) ans=u->v;//更新
if (u->ch[0]!=NULL) hj(u->ch[0],k,ans);//扫左子树看有更接近的没
} else
if (u->v<=k)
{
if (u->ch[1]!=NULL) hj(u->ch[1],k,ans);//扫右子树
}
}
int T,a,b;
int main()
{
srand(937);
scanf("%d",&T);
while (T--)//6种操作
{
scanf("%d%d",&a,&b);
if (a==1)
{
insert(root,b);
} else
if (a==2)
{
remove(root,b);
} else
if (a==3)
{
int ans3=ans(root,b);
printf("%d\n",ans3);
} else
if (a==4)
{
int ans4=sum(root,b);
printf("%d\n",ans4);
} else
if (a==5)
{
int ans5=0;
qq(root,b,ans5);
printf("%d\n",ans5);
} else
if (a==6)
{
int ans6=100000000;//毫无意义的初值
hj(root,b,ans6);
printf("%d\n",ans6);
}
}
return 0;
}