3224: Tyvj 1728 普通平衡树
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 3948 Solved: 1627
[Submit][Status][Discuss]
Description
您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：
1. 插入x数
2. 删除x数(若有多个相同的数，因只删除一个)
3. 查询x数的排名(若有多个相同的数，因输出最小的排名)
4. 查询排名为x的数
5. 求x的前驱(前驱定义为小于x，且最大的数)
6. 求x的后继(后继定义为大于x，且最小的数)
Input
第一行为n，表示操作的个数,下面n行每行有两个数opt和x，opt表示操作的序号(1<=opt<=6)
Output
对于操作3,4,5,6每行输出一个数，表示对应答案
Sample Input
10
1 106465
4 1
1 317721
1 460929
1 644985
1 84185
1 89851
6 81968
1 492737
5 493598
1 106465
4 1
1 317721
1 460929
1 644985
1 84185
1 89851
6 81968
1 492737
5 493598
Sample Output
106465
84185
492737
84185
492737
HINT
1.n的数据范围：n<=100000
2.每个数的数据范围：[-1e7,1e7]
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
const int maxn=;
int key[maxn],lc[maxn],rc[maxn],fa[maxn],siz[maxn];
int tot,root;
int T;
void update(int x){
siz[x]=siz[lc[x]]++siz[rc[x]];
}
void r_rotate(int x){
int y=fa[x];
lc[y]=rc[x];
if(rc[x]!=) fa[rc[x]]=y;
fa[x]=fa[y];
if(y==lc[fa[y]]) lc[fa[y]]=x;
else rc[fa[y]]=x;
fa[y]=x; rc[x]=y;
update(x); update(y);
}
void l_rotate(int x){
int y=fa[x];
rc[y]=lc[x];
if(lc[x]!=) fa[lc[x]]=y;
fa[x]=fa[y];
if(y==lc[fa[y]]) lc[fa[y]]=x;
else rc[fa[y]]=x;
fa[y]=x; lc[x]=y;
update(x); update(y);
}
void splay(int x,int s){
int p;
while(fa[x]!=s){
p=fa[x];
if(fa[p]==s){
if(x==lc[p]) r_rotate(x);
else l_rotate(x);
break;
}
if(x==lc[p]){
if(p==lc[fa[p]]) r_rotate(p),r_rotate(x);
else r_rotate(x),l_rotate(x);
}
else{
if(p==rc[fa[p]]) l_rotate(p),l_rotate(x);
else l_rotate(x),r_rotate(x);
}
}
if(s==) root=x;
update(x);
}
int find(int v){//查找在这棵树中键值为v的节点
int x=root;
while(x!=){
if(v<key[x]) x=lc[x];
else if(v>key[x]) x=rc[x];
else if(v==key[x]){
splay(x,);
return x;
}
}
return -;
}
void New_node(int &x,int fath,int v){//建立新节点
x=++tot;
lc[x]=rc[x]=; siz[x]=;
fa[x]=fath;
key[x]=v;
}
void insert(int v){//插入新节点
if(root==){
New_node(rc[],,v);
root=tot;
return ;
}
int p,x=root;
while(x!=){
p=x;
if(v<=key[x]) siz[x]++,x=lc[x];
else siz[x]++,x=rc[x];
}
if(v<=key[p]) New_node(lc[p],p,v);
else New_node(rc[p],p,v);
splay(tot,);
}
int getmax(int x){//找到以x为根的最大值
if(rc[x]!=) return getmax(rc[x]);
return x;
}
int getmin(int x){//找到以x为根的最小值
if(lc[x]!=) return getmin(lc[x]);
return x;
}
int getpre(int x){//找到节点x的前驱
splay(x,);
return getmax(lc[x]);
}
int getne(int x){//找到节点x的后继
splay(x,);
return getmin(rc[x]);
}
void Delete(int v){
int x=find(v);
int pp=getmax(lc[x]);
int nn=getmin(rc[x]);
if(lc[x]==||rc[x]==){
if(lc[x]==&&rc[x]==){
root=; rc[]=;
return ;
}
if(lc[x]==){
rc[]=rc[x]; fa[rc[x]]=; root=rc[x]; rc[x]=;
siz[x]=;
return ;
}
else{
rc[]=lc[x]; fa[lc[x]]=; root=lc[x]; lc[x]=;
siz[x]=;
return ;
}
}
splay(pp,);
splay(nn,root);
fa[lc[nn]]=; siz[lc[nn]]=; lc[nn]=;
update(nn); update(pp);
}
int rank(int rt,int v){//返回键值为v的节点的排名
if(rt==) return ;
if(v<=key[rt]) return rank(lc[rt],v);
else return siz[lc[rt]]++rank(rc[rt],v);
}
int findkth(int x,int k){//在以x为根的树中找第 k大
if(siz[lc[x]]+==k) return key[x];
if(siz[lc[x]]+>k) return findkth(lc[x],k);
return findkth(rc[x],k-siz[lc[x]]-);
} int pred(int rt,int v){//返回比 v小的最大的数
if(rt==) return v;
if(v<=key[rt]) return pred(lc[rt],v);
else{
int ans=pred(rc[rt],v);
if(ans==v) return key[rt];
return ans;
}
}
int succ(int rt,int v){//返回比 v大的最小的数
if(rt==) return v;
if(v>=key[rt]) return succ(rc[rt],v);
else{
int ans=succ(lc[rt],v);
if(ans==v) return key[rt];
return ans;
}
}
int main(){
freopen("phs.in","r",stdin);
freopen("phs.out","w",stdout);
scanf("%d",&T);
while (T--){
int kin,num;
scanf("%d%d",&kin,&num);
if(kin==)
insert(num);//插入
else if(kin==)
Delete(num);//删除(若有多个相同的数，只删除一个)
else if(kin==)
printf("%d\n",rank(root,num));//查询num数的排名(若有多个相同的数，因输出最小的排名)
else if (kin==)
printf("%d\n",findkth(root,num));//查询排名为x的数
else if (kin==)
printf("%d\n",pred(root,num));
else if (kin==)
printf("%d\n",succ(root,num));
}
return ;
}