1.remove中合并root的时候merge的顺序错了
2.kth中else跳错成左子树
by yyx0415 @ 2024-04-22 13:31:26
@[yyx0415](/user/1051910) 感谢，但是这份代码似乎还有其他问题，wa on7-12
```cpp
#include<bits/stdc++.h>
int root=0,tot=0;
struct FHQ_treap{
struct fhq_treap{
int l,r,val,siz,dat;
}tree[500005];
inline void update(int x){
tree[x].siz=tree[tree[x].l].siz+tree[tree[x].r].siz+1;
return ;
}
inline int newnode(int x){
tree[++tot].val=x;
tree[tot].siz=1;
tree[tot].dat=rand();
return tot;
}
inline void split(int k,int key,int &x,int &y){
if(k==0){
x=y=0;
return ;
}
if(tree[k].val<=key){
x=k;
split(tree[x].r,key,tree[x].r,y);
}
else{
y=k;
split(tree[y].l,key,x,tree[y].l);
}
update(k);
return ;
}
inline int merge(int x,int y){
if(x==0){
return y;
}
if(y==0){
return x;
}
if(tree[x].dat>tree[y].dat){
tree[x].r=merge(tree[x].r,y);
update(x);
return x;
}
else{
tree[y].l=merge(x,tree[y].l);
update(y);
return y;
}
}
//bug on last
void insert(int key){
int x,y;
split(root,key-1,x,y);
int id=newnode(key);
root=merge(merge(x,id),y);
return ;
}
void remove(int key){
int x,y,z;
split(root,key-1,x,y);
split(y,key,y,z);
if(y){
y=merge(tree[y].l,tree[y].r);
}
root=merge(merge(x,y),z);
return ;
}
int rnk(int key){
int x,y,ans;
split(root,key-1,x,y);
ans=tree[x].siz+1;
root=merge(x,y);
return ans;
}
int kth(int rnk){
int p=root;
while(p){
if(tree[tree[p].l].siz+1==rnk){
break;
}
else if(tree[tree[p].l].siz+1>rnk){
p=tree[p].l;
}
else{
rnk-=tree[tree[p].l].siz+1;
p=tree[p].r;
}
}
return tree[p].val;
}
int pre(int key){
int x,y,p;
split(root,key-1,x,y);
p=x;
while(tree[p].r!=0){
p=tree[p].r;
}
root=merge(x,y);
return tree[p].val;
}
int next(int key){
int x,y,p;
split(root,key-1,x,y);
p=y;
while(tree[p].l!=0){
p=tree[p].l;
}
root=merge(x,y);
return tree[p].val;
}
}treap;
int n;
int main(){
srand(time(0));
scanf("%d",&n);
for(int i=1;i<=n;i++){
int opt,x;
scanf("%d%d",&opt,&x);
if(opt==1){
treap.insert(x);
}
else if(opt==2){
treap.remove(x);
}
else if(opt==3){
printf("%d\n",treap.rnk(x));
}
else if(opt==4){
printf("%d\n",treap.kth(x));
}
else if(opt==5){
printf("%d\n",treap.pre(x));
}
else{
printf("%d\n",treap.next(x));
}
}
}
```
by liverxiwo @ 2024-04-23 14:03:19
已送上关注
by liverxiwo @ 2024-04-23 14:03:42
@[liverxiwo](/user/1162380) next中要按key分裂而非key-1
by yyx0415 @ 2024-04-23 22:02:50