玄学treap

看脸算法

指针真垃圾

delete 真垃圾

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         using namespace std;struct node{    int v;    int num;//有可能有多个相同的数在一棵BST中    int r;    int s;    node* ch[2];//左右孩子    node(int val):v(val)//初始化    {        r=rand();        num=1;        s=1;        ch[0]=ch[1]=NULL;    }    int cmp(int val)//比较函数    {        if(val==v)            return -1;        if(val
         
          s; if(ch[1]!=NULL) s+=ch[1]->s; }};void rotato(node* &x,int mode)//旋转函数，mode为左右旋参数{ node* k=x->ch[mode^1];//相当于1-mode，不过有常数加成 x->ch[mode^1]=k->ch[mode]; k->ch[mode]=x; x->sum();//重新计算节点个数 k->sum(); x=k;}void insert(node* &x,int val)//插入，一定要引用，不然旋转就没用了{ if(x==NULL) { x=new node(val); return ; } //printf("%d ",x->v); int d=x->cmp(val);//还是自己看cmp的返回值吧 if(d==-1) { x->num+=1; x->s+=1; return ; } else { insert(x->ch[d],val);//递归插入 if(x->ch[d]->r > x->r)//如果不满足堆性质，旋转 rotato(x,d^1); } x->sum();//重新计算个数}void remove(node* &x,int val){ if(x==NULL) return ; int d=x->cmp(val); if(d==-1) { if(x->num>1) { x->num-=1; x->s-=1; return ; } node* u=x; if(x->ch[0]!=NULL&&x->ch[1]!=NULL)//如果左右儿子都有，那样的话，我们把根节点和左右儿子中优先度最大的旋上来。直到要删除的值最多只有一个左右儿子，然后直接删除。 { int d2=( x->ch[0]->r > x->ch[1]->r ? 1 : 0); rotato(x,d2); remove(x->ch[d2],val); } else if(x->ch[0]==NULL) x=x->ch[1]; else x=x->ch[0]; //delete u; delete就是个垃圾 } else remove(x->ch[d],val); if(x!=NULL) x->sum();}int kth(node *x,int k)//第几小的数{ if (k<0||k>x->s||x==NULL) return 0; int s=(x->ch[0]==NULL ? 0 : x->ch[0]->s); if(s
          
           <=s+x->num)//照着规律查就行了。 return x->v; if(k<=s) return kth(x->ch[0],k); else return kth(x->ch[1],k-s-x->num);//在这停顿}int find(node *x,int val)//val的排名{ int d=x->cmp(val); int s=(x->ch[0]==NULL ? 0 : x->ch[0]->s); if(d==-1) return s+1; else { if(d==0) return find(x->ch[0],val); else return s+x->num+find(x->ch[1],val); }}void pre(node* x,int val,int &ans)//前驱与后继{ if(x==NULL) return; if(x->v
           
            v>ans)//更新一下 ans=x->v; if(x->ch[1]!=NULL) //遍历右子树就可以了，左子树就不用遍历了 pre(x->ch[1],val,ans); } else if(x->v>=val) if(x->ch[0]!=NULL)//这种情况就只遍历左子树就可以了 pre(x->ch[0],val,ans);}void nxt(node* x,int val,int &ans){ if(x==NULL) return; if(x->v>val) { if(x->v
            
             v; if(x->ch[0]!=NULL) nxt(x->ch[0],val,ans); } else if(x->v<=val) if (x->ch[1]!=NULL) nxt(x->ch[1],val,ans);}int read(){ int s=0,f=1; char in=getchar(); while(in<'0'||in>'9') { if(in=='-') f=-1; in=getchar(); } while(in>='0'&&in<='9') { s=(s<<1)+(s<<3)+in-'0'; in=getchar(); } return s*f;}void visit(node *x){ if(x==NULL) return ; visit(x->ch[0]); printf("%d ",x->v); visit(x->ch[1]);}//中序遍历node *root;int main(){ srand(time(NULL)); int n=read(); int a,b; int ans; for(int i=1;i<=n;i++) { a=read(); b=read(); switch(a) { case 1:insert(root,b);break; case 2:remove(root,b);break; case 3:printf("%d\n",find(root,b));break; case 4:printf("%d\n",kth(root,b));break; case 5:insert(root,b);ans=-0x7fffffff;pre(root,b,ans);printf("%d\n",ans);remove(root,b);break; case 6:insert(root,b);ans=0x7fffffff;nxt(root,b,ans);printf("%d\n",ans);remove(root,b);break; } //visit(root); //printf("\n"); }}