萌新刚学BST,按值找排名和按排名找值的地方写错了,求助
查看原帖
萌新刚学BST,按值找排名和按排名找值的地方写错了,求助
295504
Into_qwq楼主2020/7/16 10:59

RT,求助,改了好久没发现问题

错误部分的代码:

inline int fval(int f,int v){
    if (!f) return 0;
    if (v==e[f].v) return e[e[f].ls].size+1;
    if (v<e[f].v) return fval(e[f].ls,v);
    return fval(e[f].rs,v)+e[e[f].ls].size+e[f].cnt;
}
inline int frk(int f,int rk){
    if(!f) return inf;
    if (e[e[f].ls].size>=rk) return frk(e[f].ls,rk);
    if (e[e[f].ls].size+e[f].cnt>=rk) return e[f].v;
    return frk(e[f].rs,rk-e[e[f].ls].size-e[f].cnt);
}

完整代码:

#include<bits/stdc++.h>
using namespace std;
const int inf=2147483647;
int tot;
struct node{int v,ls,rs,cnt,size;}e[50010];
inline void insert(int f,int v){
    ++e[f].size;
    if(e[f].v==v){++e[f].cnt;return;}
    //insert(e[f].ls,v);
    if (e[f].v>v)
    {
        if(e[f].ls) insert(e[f].ls,v);
        else e[++tot].v=v,e[tot].size=e[tot].cnt=1,e[f].ls=tot;
    }
    else
    {
        if(e[f].rs) insert(e[f].rs,v);
        else e[++tot].v=v,e[tot].size=e[tot].cnt=1,e[f].rs=tot;
    }
}
inline int qq(int f,int v,int ans){
    if(e[f].v>=v)
        if(!e[f].ls) return ans;
        else return qq(e[f].ls,v,ans);
    else{
        if (!e[f].rs) return (e[f].v<v)?e[f].v:ans;
        if (e[f].cnt) return qq(e[f].rs,v,e[f].v);
        else return qq(e[f].rs,v,ans);}
        
}
inline int hj(int f,int v,int ans){
    if(e[f].v<=v)
        if(!e[f].rs) return ans;
        else return hj(e[f].rs,v,ans);
    else{
        if (!e[f].ls) return e[f].v>v?e[f].v:ans;
        if (e[f].cnt) return hj(e[f].ls,v,e[f].v);
        else return hj(e[f].ls,v,ans);}
}
inline int fval(int f,int v){
    if (!f) return 0;
    if (v==e[f].v) return e[e[f].ls].size+1;
    if (v<e[f].v) return fval(e[f].ls,v);
    return fval(e[f].rs,v)+e[e[f].ls].size+e[f].cnt;
}
inline int frk(int f,int rk){
    if(!f) return inf;
    if (e[e[f].ls].size>=rk) return frk(e[f].ls,rk);
    if (e[e[f].ls].size+e[f].cnt>=rk) return e[f].v;
    return frk(e[f].rs,rk-e[e[f].ls].size-e[f].cnt);
}
int main(){
    int n,k,opt,x;
    scanf("%d",&n);
    while(n--){
        scanf("%d%d",&opt,&x);
        if(opt==1) printf("%d\n",fval(1,x)+1);
        if(opt==2) printf("%d\n",frk(1,x));
        if(opt==3) printf("%d\n",qq(1,x,-inf));
        if(opt==4) printf("%d\n",hj(1,x,inf));
        if (opt==5){
            if (!tot) e[++tot].cnt=e[tot].size=1,e[tot].v=x;
            else insert(1,x);
        }
    }
    return 0;
}
2020/7/16 10:59
加载中...