@zzzc18 2017-10-23T10:04:24.000000Z 字数 1915 阅读 1061

# 非旋转式Treap FHQ_Treap

模板库 Treap

%%%%%%% Kirin %%%%%%%

[洛谷]普通平衡树

#include<cstdio>#include<cstring>#include<algorithm>#include<cstdlib>using namespace std;int n;const int MAXN = 100000+9;struct T{    int val,RD,sz,ls,rs;}tree[MAXN];int root;struct PAIR{    int first,second;    PAIR(){first=second=0;}};void update(int x){    tree[x].sz=tree[tree[x].ls].sz+tree[tree[x].rs].sz+1;}int New_Node(int x){//woooooooooooooooooooooooooooooo    static int cnt=0;    tree[++cnt].val=x;    tree[cnt].sz=1;    tree[cnt].RD=rand();    return cnt;}PAIR split(int x,int val){    PAIR re;    if(x==0){        return re;    }    if(val>=tree[x].val){        re=split(tree[x].rs,val);        tree[x].rs=re.first;        re.first=x;        update(x);    }    else{        re=split(tree[x].ls,val);        tree[x].ls=re.second;        re.second=x;        update(x);    }    return re;}int merge(int u,int v){    if(u==0 || v==0){        return u+v;    }    if(tree[u].RD<tree[v].RD){        tree[u].rs=merge(tree[u].rs,v);        update(u);        return u;    }    else{        tree[v].ls=merge(u,tree[v].ls);        update(v);        return v;    }}void insert(int val){    PAIR rt=split(root,val);    root=merge(rt.first,merge(New_Node(val),rt.second));}void del(int val){    PAIR lrt=split(root,val-1);    PAIR rrt=split(lrt.second,val);    rrt.first=merge(tree[rrt.first].ls,tree[rrt.first].rs);    root=merge(lrt.first,merge(rrt.first,rrt.second));}int n2r(int val){    PAIR rt=split(root,val-1);    int re=tree[rt.first].sz+1;    root=merge(rt.first,rt.second);    return re;}int r2n(int x,int val){    while(true){        if(tree[tree[x].ls].sz>=val){            x=tree[x].ls;        }        else if(tree[tree[x].ls].sz+1<val){            val-=tree[tree[x].ls].sz+1;            x=tree[x].rs;        }        else{            return tree[x].val;        }    }}int pred(int val){    PAIR rt=split(root,val-1);    int re=r2n(rt.first,tree[rt.first].sz);    root=merge(rt.first,rt.second);    return re;}int succ(int val){    PAIR rt=split(root,val);    int re=r2n(rt.second,1);    root=merge(rt.first,rt.second);    return re;}int main(){    scanf("%d",&n);    int i;    for(i=1;i<=n;i++){        int opt,x;        scanf("%d%d",&opt,&x);        if(opt==1)insert(x);        if(opt==2)del(x);        if(opt==3){printf("%d\n",n2r(x));}        if(opt==4){printf("%d\n",r2n(root,x));}        if(opt==5){printf("%d\n",pred(x));}        if(opt==6){printf("%d\n",succ(x));}    }    return 0;}

• 私有
• 公开
• 删除