很奇怪啊,平衡树的二叉搜索树基础都是用的这个代码过的。怎么这个就过不了?
#include<cstdio>
const int INF = 2147483647;
const int N = 1e4+5;
int q, opt, x, cnt, root;
struct BST{
int data, left, right, siz;
}t[N];
void up(int now)
{
t[now].siz = t[t[now].left].siz+t[t[now].right].siz+1;
}
void insert(int &now, int data)
{
if (now==0){
now = ++cnt;
t[now] = BST{data, 0, 0, 1};
return ;
}
++t[now].siz;
if (data>=t[now].data) insert(t[now].right, data);
else insert(t[now].right, data);
up(now);
}
int rank(int now, int data)//查询某一节点的排名
{
if (!now) return 0;
if (data>t[now].data) return t[t[now].left].siz+1+rank(t[now].right,data);
return rank(t[now].left, data);
}
int find(int now, int rank)
{
if (rank==t[t[now].left].siz+1) return t[now].data;
else if (rank>t[t[now].left].siz+1) return find(t[now].right, rank-t[t[now].left].siz-1);
else return find(t[now].left, rank);
}
int query_pre(int now, int data)
{
if (now==0) return 0;
if (data<=t[now].data) return query_pre(t[now].left, data);
int tmp=query_pre(t[now].right, data);
return tmp==0?t[now].data:tmp;
}
int query_suf(int now, int data)
{
if (now==0) return 0;
if (data>=t[now].data) return query_suf(t[now].right, data);
int tmp=query_suf(t[now].left, data);
return tmp==0?t[now].data:tmp;
}
inline int read()
{
int x=0, f=1; char c=getchar();
while (!(c>='0' && c<='9')){if (c=='-') f=-1; c=getchar();}
while (c>='0' && c<='9'){x=(x<<3)+(x<<1)+c-48; c=getchar();}
return f*x;
}
int main()
{
q=read();
while (q--){
opt=read(), x=read();
if (opt==1) printf("%d\n", rank(root, x)+1);
else if (opt==2) printf("%d\n", find(root, x));
else if (opt==3){
int ans=query_pre(root, x);
printf("%d\n", !ans?-INF:ans);
}
else if (opt==4){
int ans=query_suf(root, x);
printf("%d\n", !ans?INF:ans);
}
else insert(root, x);
}
return 0;
}