指针版平衡树求助
查看原帖
指针版平衡树求助
248895
Astk楼主2020/9/5 10:52

最近两天在搞平衡树,搞得自己都恶心了,两页的提交记录红绿相间。

蒟蒻突然不想数组转指针了,但写都写了,不调出来,怪不舒服的。。。。。。。求助大佬

#include<cstdio>
#include<cstdlib>
#define INF 0x7fffffff
using namespace std;
const int N=1e5+10;
struct Treap{
    Treap *ch[2];
    int dat,val,cnt,siz;
    Treap(int v):dat=rand(),val=v,cnt=siz=1,ch[0]=ch[1]=NULL{}
    int cmp(int x)const{
        if(x==val) return -1;
        return x>val;
    }
    up(){
        siz=cnt;
        if(ch[0]!=NULL) siz+=ch[0]->siz;
        if(ch[1]!=NULL) siz+=ch[1]->siz;
    }
};
// Treap *null=new Treap();
Treap* root;
void rotate(Treap* &o,int d){
    Treap* k=o->ch[d^1];
    o->ch[d^1]=k->ch[d];
    k->ch[d]=o;
    o=k;
    o->ch[d]->up();
    o->up();
}
void insert(Treap* &o,int x){
    if(o==NULL) o=new Treap(x);
    else{
        int d=o->cmp(x);
        if(d==-1){a[o].cnt++,o->up();return;}
        insert(o->ch[d],x);o->up();
        if(o->ch[d]->dat>o->dat) rotate(o,d^1);
    }
}
void remove(Treap* &o,int x){
    if(o==NULL) return;
    int d=o->cmp(x);
    if(d==-1){
        if(o->cnt>1){o->cnt--,o->up();return;}
        if(o->ch[0]==NULL) o=o->ch[1];
        else if(o->ch[1]==NULL) o=o->ch[0];
        else{
            int d2=o->ch[0]->dat>a->o->ch[1]->dat;
            rotate(o,d2);remove(o->ch[d2],x);
        }
    }
    else remove(o->ch[d],x);
    up(o);
}
int getpre(Treap* o,int val){
    Treap* ans;
    while(o!=NULL){
        if(o->val>=val) o=o->ch[0];
        else ans=o,o=o->ch[1];
    }
    return ans->val;
}
int getsuc(Treap* o,int val){
    Treap* ans;
    while(o!=NULL){
        if(o->val<=val) o=o->ch[1];
        else ans=o,o=o->ch[0];
    }
    return ans->val;
}
int getk(Treap* o,int rank){
    if(o->ch[0]->siz>=rank) return getk(o->ch[0],rank);
    if(o->cnt+o->ch[0]->siz>=rank) return a[o].val;
    return getk(o->ch[1],rank-o->cnt-o->ch[0]->cnt);
}
int getkth(Treap* o,int val){
    if(val==o->val) return o->ch[0]->siz+1;
    if(val<o->val) return getkth(o->ch[0],val);
    return getkth(o->ch[1],val)+o->cnt+o->ch[0]->siz;
}
int n,opt,x;
int main(){
    scanf("%d",&n);
    while(n--){
        scanf("%d%d",&opt,&x);
        switch(opt){
            case 1:insert(root,x);break;
            case 2:remove(root,x);break;
            case 3:printf("%d\n",getkth(root,x));break;
            case 4:printf("%d\n",getk(root,x));break;
            case 5:printf("%d\n",getpre(root,x));break;
            case 6:printf("%d\n",getpre(root,x));break;
        }
    }
}
2020/9/5 10:52
加载中...