不是你不给代码看什么？
by _QrSn_ @ 2023-12-26 12:10:56
**代码如下：**
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+3,INF=2147483647;
struct TREE{
int val,ls,rs,cnt,siz;
}tr[N];
//val为当前节点的值,ls,rs为左右指针
//cnt为当前节点出现的次数，siz为当前子树节点树
int tn;
void add(int r,int v){
tr[r].siz++; //该节点大小增大
if(tr[r].val==v){ //找到相同值
tr[r].cnt++;
return;
}
if(v<tr[r].val){ //往左子树加
if(tr[r].ls==0){
++tn;
tr[r].ls=tn;
tr[tn].val=v;
tr[tn].cnt=tr[tn].siz=1;
}
else{
add(tr[r].ls,v);
}
}
else{//往右子树加
if(tr[r].rs==0){
++tn;
tr[r].rs=tn;
tr[tn].val=v;
tr[tn].cnt=tr[tn].siz=1;
}
else add(tr[r].rs,v);
}
}
int findFr(int r,int x,int ans){ //ans为已经查到的最大前驱值
if(tr[r].val>=x){ //到左子树找前驱
if(tr[r].ls==0)
return ans;
else
return findFr(tr[r].ls,x,ans);
}
else{ //当前节点值小于x,当前子树都是x的前驱
if(tr[r].rs==0) //没有右节点，没有更大前驱了
return tr[r].val;
else
return findFr(tr[r].rs,x,tr[r].val);//前驱值也更新
}
}
int findNx(int r,int x,int ans){ //ans为已经查到的最大前驱值
if(tr[r].val<=x){ //到右子树找后继
if(tr[r].rs==0) //没有右子节点返回
return ans;
else
return findNx(tr[r].rs,x,ans);
}
else{ //当前节点值大于x,当前子树都是x的后继
if(tr[r].ls==0) //没有左节点，没有更小后继了
return tr[r].val;
else
return findNx(tr[r].ls,x,tr[r].val);//前后继也更新
}
}
int findVal(int r,int x){
if (r==0) return 0;
if(tr[r].val==x) return tr[tr[r].ls].siz;
if(tr[r].val>x) return findVal(tr[r].ls,x);
return findVal(tr[r].rs,x)+tr[tr[r].ls].siz+tr[r].cnt;
}
int findRk(int r,int x){
if(r==0) return INF;
if(tr[tr[r].ls].siz>=x) return findRk(tr[r].ls,x);
if(tr[r].cnt+tr[tr[r].ls].siz>=x) return tr[r].val;
return findRk(tr[r].rs,x-tr[r].cnt-tr[tr[r].ls].siz);
//去掉根和左子树排名，再在右子树按新排名找
}
int main() {
int q,op,x;
scanf("%d",&q);
while(q--){
scanf("%d%d",&op,&x);
switch(op){
case 1:
printf("%d\n",findVal(1,x)+1);
break;
case 2:
printf("%d\n",findRk(1,x));
break;
case 3:
printf("%d\n",findFr(1,x,-INF));
break;
case 4:
printf("%d\n",findNx(1,x,INF));
break;
case 5:
if(tn==0){
++tn;
tr[tn].val=x;
tr[tn].cnt=tr[tn].siz=1;
}
else add(1,x);
break;
}
}
return 0;
}
```
by youyukyc @ 2023-12-26 12:11:44
@[_QrSn_](/user/511253) 代码在下面
by youyukyc @ 2023-12-26 20:12:29
@[_QrSn_](/user/511253) 谢谢，代码贴在下面了的
by youyukyc @ 2023-12-26 20:13:29
@[youyukyc](/user/135799) 第六个点是某个毒瘤添加的hack，是在没有insert的时候查询pre与next，所以会re。
by litjohn @ 2024-02-06 19:06:21