```cpp
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
const int INF = 0x3f3f3f3f;
struct treap{
int l,r;
int val,dat;
int cnt,size;
}a[N];
int tot,root,n;
int New(int val){
a[++tot].val = val;
a[tot].dat = rand();
a[tot].cnt = a[tot].size = 1;
return tot;
}
void update(int p){
a[p].size = a[a[p].l].size + a[a[p].r].size + a[p].cnt;
}
void Build(){
New(-INF);
New(INF);
root = 1;
a[1].r = 2;
update(root);
}
int getRank(int p,int val){
if(p == 0){
return 0;
}else if(val == a[p].val){
return a[a[p].l].size + 1;
}else if(val < a[p].val){
return getRank(a[p].l,val);
}else{
return getRank(a[p].r,val) + a[a[p].l].size + a[p].cnt;
}
}
int getVal(int p,int rank){
if(p == 0){
return INF;
}
if(a[a[p].l].size >= rank){
return getVal(a[p].l,rank);
}else if(a[a[p].l].size + a[p].cnt >= rank){
return a[p].val;
}else{
return getVal(a[p].r,rank-a[a[p].l].size-a[p].cnt);
}
}
void zig(int &p){
int q = a[p].l;
a[p].l = a[q].r;
a[q].r = p;
p = q;
update(a[p].r);
update(p);
}
void zag(int &p){
int q = a[p].r;
a[p].r = a[q].l;
a[q].l = p;
p = q;
update(a[p].l);
update(p);
}
void insert(int &p,int val){
if(p == 0){
p = New(val);
return;
}else if(val == a[p].val){
a[p].cnt ++;
update(p);
return;
}else if(val < a[p].val){
insert(a[p].l,val);
if(a[p].dat < a[a[p].l].dat){
zig(p);
}
update(p);
return;
}else{
insert(a[p].r,val);
if(a[p].dat < a[a[p].r].dat){
zag(p);
}
update(p);
return;
}
}
int getpre(int val){
int ans = 1;
int p = root;
while(p){
if(val == a[p].val){
if(a[p].l > 0){
p = a[p].l;
while(a[p].r > 0){
p = a[p].r;
}
ans = p;
}
break;
}
if(a[p].val < val && a[p].val > a[ans].val){
// a[ans].val < a[p].val < val;
ans = p;
}
p = val < a[p].val ? a[p].l : a[p].r;
}
return a[ans].val;
}
int getnext(int val){
int ans = 2;
int p = root;
while(p){
if(val == a[p].val){
if(a[p].r > 0){
p = a[p].r;
while(a[p].l > 0){
p = a[p].l;
}
ans = p;
}
break;
}
if(a[p].val > val && a[p].val < a[ans].val){
// a[ans].val > a[p].val > val;
ans = p;
}
p = val < a[p].val ? a[p].l : a[p].r;
}
return a[ans].val;
}
void remove(int &p,int val){
if(p == 0){
return;
}
if(val == a[p].val){
if(a[p].cnt > 1){
a[p].cnt --;
update(p);
return;
}else if(a[p].l || a[p].r){//非叶子节点;
if(a[p].r == 0 || a[a[p].l].dat > a[a[p].r].dat){
zig(p);//右旋;
remove(a[p].r,val);
}else{
zag(p);
remove(a[p].l,val);
}
update(p);
return;
}else{//叶子节点;
p = 0;
return;
}
}else if(val < a[p].val){
remove(a[p].l,val);
}else{
remove(a[p].r,val);
}
}
int main(){
srand(time(0));
Build();
scanf("%d",&n);
while(n --){
int opt,x;
scanf("%d%d",&opt,&x);
switch(opt){
case 1:
insert(root,x);
break;
case 2:
remove(root,x);
break;
case 3:
printf("%d\n",getRank(root,x)-1);
break;
case 4:
printf("%d\n",getVal(root,x+1));
break;
case 5:
printf("%d\n",getpre(x));
break;
case 6:
printf("%d\n",getnext(x));
break;
}
}
}
```
by WhileTrueRP @ 2023-11-17 10:11:38
@[WhileTrueRP](/user/373198) 平衡树最好不要这样写...把引用传来传去会引起很多麻烦...
by Liuyuzhuo @ 2023-11-17 10:59:32
@[Liuyuzhuo](/user/221575) 所以该怎么写
by WhileTrueRP @ 2023-11-17 11:10:43
@[WhileTrueRP](/user/373198) 删除后要加update
by Liuyuzhuo @ 2023-11-17 11:22:44
@[WhileTrueRP](/user/373198) 第四种操作 p=0 时应该返回1
by Liuyuzhuo @ 2023-11-17 11:26:38
@[WhileTrueRP](/user/373198)
调出来了，把$remove()$里的$update()$放到函数最后面，把return删了。因为有可能查询的数在平衡树中不存在，把$getRank()$里$val=a[p].val$时返回左子树$size+1$变成$size$,然后主函数里调用函数后再$+1$
```
int getRank(int p,int val){if(p == 0){
return 0;
}else if(val == a[p].val){
return a[a[p].l].size;
}else if(val < a[p].val){
return getRank(a[p].l,val);
}else{
return getRank(a[p].r,val) + a[a[p].l].size + a[p].cnt;
}
}
（主函数中）
case 3:
printf("%d\n",getRank(root,x));
break;
void remove(int &p,int val){
if(p == 0){
return;
}
if(val == a[p].val){
if(a[p].cnt > 1){
a[p].cnt --;
}else if(a[p].l || a[p].r){//非叶子节点;
if(a[p].r == 0 || a[a[p].l].dat > a[a[p].r].dat){
zig(p);//右旋;
remove(a[p].r,val);
}else{
zag(p);
remove(a[p].l,val);
}
update(p);
}else{//叶子节点;
p = 0;
}
}else if(val < a[p].val){
remove(a[p].l,val);
}else{
remove(a[p].r,val);
}update(p);
}
```
by Chipsignature @ 2023-11-17 11:33:15
否则会**WA**#1和#2
by Chipsignature @ 2023-11-17 11:36:53
@[Chipsignature](/user/515557) @[Liuyuzhuo](/user/221575) 已关注
by WhileTrueRP @ 2023-11-17 11:45:13