求助无旋treap,一直mle

回复帖子

@cjhspeed 2021-02-23 17:41 回复
#include<bits/stdc++.h>
using namespace std;

const int N=5e5+5;

int n,cnt=0,root=0;

struct {
    int fa,ls,rs;
    int val,rnd,siz;
}t[N];

int new_p(int a){
    t[++cnt].siz=1;
    t[cnt].rnd=rand();
    t[cnt].val=a;
    return cnt;
} 

void update(int x){
    t[x].siz=t[t[x].ls].siz+t[t[x].rs].siz+1;
}

void split(int now,int k,int &x,int &y){
    if(!now) x=y=0;
    else {
        if(t[now].val<=k){
            x=now;
            split(t[now].rs,k,t[now].rs,y);
        } else {
            y=now;
            split(t[now].ls,k,x,t[now].ls);
        }
        update(now);
    }
}

int Merge(int x,int y){
    if(!x || !y) return x+y;
    if(t[x].rnd<t[y].rnd){
        t[x].rs=Merge(t[x].rs,y);
        update(x); 
        return x;
    } else {
        t[y].ls=Merge(x,t[y].ls);
        update(y);
        return y;
    }
}
int x,y,z;

void insert(int ver){
    split(root,ver,x,y);
    root=Merge(Merge(x,new_p(ver)),y);
}

void Delete(int a){
    split(root,a,x,z);
    split(root,a-1,x,y);
    y=Merge(t[y].ls,t[y].rs);
    root=Merge(Merge(x,y),z);
}

void get_rand(int ver){
    split(root,ver-1,x,y);
    printf("%d\n",t[x].siz+1);
    root=Merge(x,y);
}

void kth(int k){
    int now=root;
    while(1){
        if(t[t[now].ls].siz>=k) now=t[now].ls;
        else if(k==t[t[now].ls].siz+1) break;
        else k-=t[t[now].ls].siz+1,now=t[now].rs;
    }
    printf("%d\n" , t[now].val) ;
}

void get_pre(int ver){
    split(root,ver-1,x,y);
    int cur=x;
    while(t[cur].rs) cur=t[cur].rs;
    printf("%d\n" , t[cur].val) ;
    root=Merge(x,y);
}

void get_nxt(int ver){
    split(root,ver,x,y);
    int cur=y;
    while(t[cur].ls) cur=t[cur].ls;
    printf("%d\n" , t[cur].val) ;
    root=Merge(x,y);
}

int main(){
    srand(time(0));
    scanf("%d",&n);
    while(n--){
        int op,x;
        scanf("%d%d",&op,&x);
        if(op==1){
            insert(x);
        } else if(op==2){
            Delete(x);
        } else if(op==3){
            get_rand(x);
        } else if(op==4){
            kth(x);
        } else if(op==5){
            get_pre(x);
        } else if(op==6){
            get_nxt(x);
        }
    }
    return 0;
}

向各位巨佬请教

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。