3224: Tyvj 1728 普通平衡树
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 7390 Solved: 3122
[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]
数据如下http://pan.baidu.com/s/1jHMJwO2
treap的模板题，涉及了treap的各种操作
操作函数中运用了传引用的方式改变上一层结点的子节点值，很方便
/*by SilverN*/
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
int n;
struct treap{
int l,r;//左右子树
int val,ct;//值 重复次数
int size,rand;//管控数量，随机权值
}t[];
int root=,cnt=;
int ans;
void update(int k){
t[k].size=t[t[k].l].size+t[t[k].r].size+t[k].ct;
}
void lt(int &k){//左旋
int now=t[k].r;
t[k].r=t[now].l;
t[now].l=k;
t[now].size=t[k].size;
update(k);
k=now;
return;
}
void rt(int &k){
int now=t[k].l;
t[k].l=t[now].r;
t[now].r=k;
t[now].size=t[k].size;
update(k);
k=now;
return;
}
void insert(int &k,int x){//&k是为了建新节点 x为插入值
if(k==){//建新节点
t[++cnt].val=x;
t[cnt].size=;
t[cnt].ct=;
t[cnt].rand=rand();
k=cnt;
return;
}
t[k].size++;
if(t[k].val==x) t[k].ct++;//与节点等值
else if(x>t[k].val){
insert(t[k].r,x);
if(t[t[k].r].rand<t[k].rand) lt(k);
}else{//x<t[k].val
insert(t[k].l,x);
if(t[t[k].l].rand<t[k].rand) rt(k);
}
return;
}
void del(int &k,int x){
if(k==)return;
if(t[k].val==x){
if(t[k].ct>){t[k].ct--;t[k].size--;return;}
if(t[k].l*t[k].r==)k=t[k].l+t[k].r;//如果k是链结点(只有一个子节点)，由其子节点补位
else{
if(t[t[k].l].rand<t[t[k].r].rand){
rt(k);
del(k,x);
}
else{
lt(k);
del(k,x);
}
}
return; }
t[k].size--;
if(x>t[k].val)del(t[k].r,x);
if(x<t[k].val)del(t[k].l,x);
return;
}
void ask_p(int k,int x,int mode){//前驱 //mode==1 ->前驱 mode==2 ->后驱
if(mode==){
if(!k)return;
if(t[k].val<x){//依照二叉树的性质，要找小的往左查，要找大的往右查
ans=t[k].val;
ask_p(t[k].r,x,);
}else ask_p(t[k].l,x,);
return;
}
if(mode==){
if(!k)return;
if(t[k].val>x){
ans=t[k].val;
ask_p(t[k].l,x,);
}else ask_p(t[k].r,x,);
}
return;
}
int ask_rank(int k,int x){//已知数字问排名
if(!k)return ;
if(t[k].val==x)return t[t[k].l].size+;
if(t[k].val<x)return t[k].ct+t[t[k].l].size+ask_rank(t[k].r,x);
else return ask_rank(t[k].l,x);
}
int ask_num(int k,int x){// 已知排名问数字
if(!k)return ;
if(x<=t[t[k].l].size)return ask_num(t[k].l,x);//排名小于左子树包含结点数量，则往左查
if(x>t[t[k].l].size+t[k].ct)return ask_num(t[k].r,x-t[t[k].l].size-t[k].ct);
//排名大于“左子树结点数加父结点重复数”，则往右查
else return t[k].val;//否则返回父结点值
}
int main(){
int opt,x;
scanf("%d",&n);
while(n--){
scanf("%d%d",&opt,&x);
switch(opt){
case : insert(root,x); break;
case : del(root,x); break;
case : printf("%d\n",ask_rank(root,x)); break;
case : printf("%d\n",ask_num(root,x)); break;
case : ask_p(root,x,);printf("%d\n",ans);break;//前驱
case : ask_p(root,x,);printf("%d\n",ans);break;//前驱
}
// for(int i=1;i<=cnt;i++)printf("%d ",t[i].val);
// cout<<endl;
}
return ;
}