@[vectorwyx](/user/238408) 因为O2已经救不了BST了。。。一开始MLE可能是递归层数过多爆栈。。
by 枫初音斗颂皮 @ 2020-02-09 09:36:18
@[枫初音斗颂皮](/user/107880) 但是，为什么我的同学用BST只T了一个点呢？
by vectorwyx @ 2020-02-09 09:40:38
@[vectorwyx](/user/238408) 显然这几个点是专门卡BST的，再吸氧也没法过。
这边表示如果用bfs的方式的话不吸氧也能不MLE
by yummy @ 2020-02-09 09:40:49
@[vectorwyx](/user/238408) 本蒟蒻的平衡二叉树可以AC，但我加了很多神奇的算法优化
by judgejudge @ 2020-02-09 09:41:01
@[yummy](/user/101694) 但是我的代码和我的同学的代码思路是一样的啊，这是我同学的代码：
```cpp
#include<cstdio>
#include<algorithm>
#define N 100010
using namespace std;
struct Node{
int l,r;
int data;
int siz,cnt;
}t[N];
int n,cnt,root;
void pushup(int rt){
int l=t[rt].l;
int r=t[rt].r;
t[rt].siz=t[l].siz+t[r].siz+t[rt].cnt;
}
void insert(int &rt,int x){
if(rt==0){
rt=++cnt;
t[rt].data=x;
t[rt].cnt=t[rt].siz=1;
return;
}
// rebuild(rt);
if(t[rt].data==x){
t[rt].cnt++;
t[rt].siz++;
return;
}
if(t[rt].data>x){
insert(t[rt].l,x);
pushup(rt);
return;
}
if(t[rt].data<x){
insert(t[rt].r,x);
pushup(rt);
return;
}
}
int delmin(int &rt){
if(t[rt].l){
int ret=delmin(t[rt].l);
pushup(rt);
return ret;
}
int ret=rt;
rt=t[rt].r;
return ret;
}
void del(int &rt,int x){
if(t[rt].data>x){
del(t[rt].l,x);
pushup(rt);
}
if(t[rt].data<x){
del(t[rt].r,x);
pushup(rt);
}
if(t[rt].data==x){
if(t[rt].cnt>1){
t[rt].cnt--;
t[rt].siz--;
return;
}
if(t[rt].l==0){
rt=t[rt].r;
return;
}
if(t[rt].r==0){
rt=t[rt].l;
return;
}
int tmp=delmin(t[rt].r);
t[rt].data=t[tmp].data;
t[rt].cnt=t[tmp].cnt;
pushup(rt);
return;
}
}
int getk(int rt,int x){
if(t[rt].data==x) return t[t[rt].l].siz+1;
if(t[rt].data<x) return (t[rt].siz-t[t[rt].r].siz)+getk(t[rt].r,x);
if(t[rt].data>x) return getk(t[rt].l,x);
}
int getkth(int rt,int x){
if(t[t[rt].l].siz+1<=x&&x<=t[t[rt].l].siz+t[rt].cnt) return t[rt].data;
if(t[t[rt].l].siz+1>x) return getkth(t[rt].l,x);
if(x>t[t[rt].l].siz+t[rt].cnt) return getkth(t[rt].r,x-(t[t[rt].l].siz+t[rt].cnt));
}
int getpre(int rt,int x){
int p=rt,ans;
while(p){
if(x<=t[p].data){
p=t[p].l;
}else{
ans=p;
p=t[p].r;
}
}
return ans;
}
int getsuc(int rt,int x){
int p=rt,ans;
while(p){
if(x>=t[p].data){
p=t[p].r;
}else{
ans=p;
p=t[p].l;
}
}
return ans;
}
int main(){
scanf("%d",&n);
while(n--){
int opt,x;
scanf("%d%d",&opt,&x);
if(opt==1){
insert(root,x);
}
if(opt==2){
del(root,x);
}
if(opt==3){
printf("%d\n",getk(root,x));
}
if(opt==4){
printf("%d\n",getkth(root,x));
}
if(opt==5){
printf("%d\n",t[getpre(root,x)].data);
}
if(opt==6){
printf("%d\n",t[getsuc(root,x)].data);
}
}
return 0;
}
```
然后我用他的代码提交[只T了最后一个点](https://www.luogu.com.cn/record/30324120)
by vectorwyx @ 2020-02-09 09:45:01
@[judgejudge](/user/133986) （平衡二叉树是什么树）
by 白鲟 @ 2020-02-09 09:45:25
@[白鲟](/user/67952) 说白了就是区间二分
by judgejudge @ 2020-02-09 09:47:22
@[白鲟](/user/67952) 只是趋于一种平衡稳定的结构罢了
by judgejudge @ 2020-02-09 09:47:47
$QAQ$关于$BST$
~~[关于平衡树](https://www.luogu.com.cn/discuss/show/137272)~~
by UnyieldingTrilobite @ 2020-02-09 09:53:41
@[return20071007](/user/250637) 禁止玩梗
by 诱宵美⑨ @ 2020-02-09 10:08:48