@zzzc18
2017-06-18T15:42:03.000000Z
字数 4532
阅读 1293
洛谷
Treap
Treap其实就是tree+heap
利用随机数给么个节点加上第二个值以实现更稳定的平衡
和Splay类似,都要旋转,不过这个是按堆的性质旋转,好写
#include<cstdio>
#include<cstdlib>
#define MAXN 1000009
using namespace std;
struct T{
int ls,rs,rd,sz,num,val;
}tree[MAXN];
int root,size,ans;
int m;
void update(int x){
tree[x].sz=tree[tree[x].ls].sz+tree[tree[x].rs].sz+tree[x].num;
}
void rotate_l(int &k){
int y=tree[k].rs;
tree[k].rs=tree[y].ls;
tree[y].ls=k;
tree[y].sz=tree[k].sz;
update(k);
k=y;
}
void rotate_r(int &k){
int y=tree[k].ls;
tree[k].ls=tree[y].rs;
tree[y].rs=k;
tree[y].sz=tree[k].sz;
update(k);
k=y;
}
void insert(int &k,int v){
if(k==0){
size++;k=size;tree[k].val=v;
tree[k].sz=tree[k].num=1;tree[k].rd=rand();
return;
}
tree[k].sz++;
if(tree[k].val==v){
tree[k].num++;
}
else if(v>tree[k].val){
insert(tree[k].rs,v);
if(tree[tree[k].rs].rd<tree[k].rd)rotate_l(k);
}
else{
insert(tree[k].ls,v);
if(tree[tree[k].ls].rd<tree[k].rd)rotate_r(k);
}
}
void del(int &k,int v){
if(k==0)return;
if(tree[k].val==v){
if(tree[k].num>1){
tree[k].sz--;tree[k].num--;
return;
}
if(tree[k].ls==0 || tree[k].rs==0)k=tree[k].ls+tree[k].rs;
else if(tree[tree[k].ls].rd<tree[tree[k].rs].rd){
rotate_r(k);
del(k,v);
}
else{
rotate_l(k);
del(k,v);
}
}
else if(tree[k].val<v){
tree[k].sz--;
del(tree[k].rs,v);
}
else{
tree[k].sz--;
del(tree[k].ls,v);
}
}
int atrank(const int &k,int x){
if(k==0)return 0;
if(tree[k].val==x)
return tree[tree[k].ls].sz+1;
else if(tree[k].val<x)
return tree[tree[k].ls].sz+tree[k].num+atrank(tree[k].rs,x);
else
return atrank(tree[k].ls,x);
}
int rerank(const int &k,int x){
if(k==0) return 0;
if(x<=tree[tree[k].ls].sz) return rerank(tree[k].ls,x);
else if(x>tree[tree[k].ls].sz+tree[k].num)return rerank(tree[k].rs,x-tree[k].num-tree[tree[k].ls].sz);
else return tree[k].val;
}
void pred(const int &k,int x){
if(k==0)return;
if(tree[k].val<x){
ans=k;
pred(tree[k].rs,x);
}
else{
pred(tree[k].ls,x);
}
}
void succ(const int &k,int x){
if(k==0)return;
if(tree[k].val>x){
ans=k;
succ(tree[k].ls,x);
}
else
succ(tree[k].rs,x);
}
int main(){
freopen("treap.in","r",stdin);
scanf("%d",&m);
while(m--){
int opt,x;ans=0;
scanf("%d%d",&opt,&x);
if(opt==1) insert(root,x);
if(opt==2) del(root,x);
if(opt==3) printf("%d\n",atrank(root,x));
if(opt==4) printf("%d\n",rerank(root,x));
if(opt==5) {pred(root,x);printf("%d\n",tree[ans].val);}
if(opt==6) {succ(root,x);printf("%d\n",tree[ans].val);}
}
return 0;
}
注释版
#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
struct TREAP{
int l,r,val,sz,recy,rd;
//sz表示树的节点数,recy记录自己被重复了几次
//rd表示该节点的优先级
}t[1000000];
int m,size,root;
void update(int k){
t[k].sz=t[t[k].l].sz+t[t[k].r].sz+t[k].recy;
//更新维护
}
void left_rotate(int &k){
int y=t[k].r;t[k].r=t[y].l;t[y].l=k;
t[y].sz=t[k].sz;update(k);k=y;
//左旋,至于这里的k=y,由于下面的递归调用,
//它会一直迭代,所以无需担心会有什么错误
}
void right_rotate(int &k){
int y=t[k].l;t[k].l=t[y].r;t[y].r=k;
t[y].sz=t[k].sz;update(k);k=y;
//右旋
}
//以下函数的调用中(int k)表示在根为k的子树中
void insert(int &k,int x){//插入操作
if (k==0){//无节点时特判,
//或是递归的边界,即插入叶节点
++size;k=size;t[k].sz=t[k].recy=1;
t[k].val=x;t[k].rd=rand();return ;
//rand()生成随机的优先级,保证了期望复杂度
}
++t[k].sz;//每次向下找同时增加该节点1个节点数
if (t[k].val==x) ++t[k].recy;
//如果是相同数字,只需++recy即可
else if (x>t[k].val){
insert(t[k].r,x);
if (t[t[k].r].rd<t[k].rd) left_rotate(k);
//插入后如果违反堆性质,就进行上浮
}else{
insert(t[k].l,x);
if (t[t[k].l].rd<t[k].rd) right_rotate(k);
}
}
void del(int &k,int x){
if (k==0) return ;//无节点就跳出
if (t[k].val==x){
if (t[k].recy>1){
--t[k].recy;--t[k].sz;return ;
//如果重复了,只需--recy即可
}
if (t[k].l*t[k].r==0) k=t[k].l+t[k].r;
//如果左右儿子有为空的情况
//或将其变为其儿子节点,或将其删除
else if (t[t[k].l].rd<t[t[k].r].rd)
right_rotate(k),del(k,x);
//如果其左右儿子都有,选择优先级较大的,
//保持以后的堆性质,同时将k节点下沉
else left_rotate(k),del(k,x);
}
else if (x>t[k].val)
--t[k].sz,del(t[k].r,x);
//如果关键值不同,继续向下找
else --t[k].sz,del(t[k].l,x);
}
int atrank(int k,int x){//寻找值为x的数的排名
if (k==0) return 0;
if (t[k].val==x) return t[t[k].l].sz+1;
//如果找的关键字,根据BST的性质,
//则其排名为左子树的大小+1
else if (x>t[k].val)
return t[t[k].l].sz+t[k].recy+atrank(t[k].r,x);
//加上前面所有比它小的数,在右子树中找
else return atrank(t[k].l,x);
//如果在左子树中找的话就不用加了
}
int rerank(int k,int x){//寻找排名为x的数值
if (k==0) return 0;
if (x<=t[t[k].l].sz) return rerank(t[k].l,x);
//如果x小于了左子树的大小,那解一定在左子树中
else if (x>t[t[k].l].sz+t[k].recy)
return rerank(t[k].r,x-t[k].recy-t[t[k].l].sz);
//如果x大于的左子树的大小+k的重复次数,
//那就在右子树中找
else return t[k].val;
//否则就是找到解了(包含了重复数字中)
}
void pred(int k,int x){//找前缀
if (k==0) return ;
if (t[k].val<x){
ans=k;pred(t[k].r,x);
//找到了更优的解,就替换之
//而且在其右子树中不可能再有更优的了
//故向其左子树中找
}else pred(t[k].l,x);
//否则就往右子树中找
}
void succ(int k,int x){//找后缀
if (k==0) return ;
if (t[k].val>x){
ans=k;succ(t[k].l,x);
}else succ(t[k].r,x);
}
int main(){
int f,x;
scanf("%d",&m);
for (int i=1;i<=m;++i){
scanf("%d%d",&f,&x);ans=0;
if (f==1) insert(root,x);
if (f==2) del(root,x);
if (f==3) printf("%d\n",atrank(root,x));
if (f==4) printf("%d\n",rerank(root,x));
if (f==5) {pred(root,x);printf("%d\n",t[ans].val);}
if (f==6) {succ(root,x);printf("%d\n",t[ans].val);}
}
return 0;
}