柒葉灬 的博客

柒葉灬 的博客

无旋treap

posted on 2019-08-21 21:37:17 | under 算法学习 |

无旋treap


代码:

#include<bits/stdc++.h>

using namespace std;
const int maxn=1e5+100;

int n;
int tot,root;
int son[maxn][2],sz[maxn],val[maxn],rnd[maxn];
int newnode(int x){
    sz[++tot]=1;
    val[tot]=x;
    rnd[tot]=rand();
    return tot;
}
void up(int p){
    sz[p]=sz[son[p][0]]+sz[son[p][1]]+1;
}
int merge(int a,int b){
    if(!a||!b)return a|b;
    if(rnd[a]<rnd[b]){
        son[a][1]=merge(son[a][1],b);
        up(a);
        return a;
    }else {
        son[b][0]=merge(a,son[b][0]);
        up(b);
        return b;
    }
}
void split(int now,int K,int &x,int &y){
    if(!now){
        x=0,y=0;
        return;
    }
    if(val[now]<=K){
        x=now;
        split(son[now][1],K,son[now][1],y);
    }else {
        y=now;
        split(son[now][0],K,x,son[now][0]);
    }
    up(now);
}
void insert(int val){
    int x,y;
    split(root,val,x,y);
    root=merge(merge(x,newnode(val)),y);
}
void del(int val){
    int x,y,z;
    split(root,val,x,z);
    split(x,val-1,x,y);
    y=merge(son[y][0],son[y][1]);
    root=merge(merge(x,y),z);
}
int Kth(int root,int K){
    int x=root;
    while(1){
        if(sz[son[x][0]]>=K)x=son[x][0];
        else if(sz[son[x][0]]+1==K)return val[x];
        else K-=sz[son[x][0]]+1,x=son[x][1];
    }
}
int Rank(int val){
    int x,y;
    split(root,val-1,x,y);
    int res=sz[x]+1;
    root=merge(x,y);
    return res;
}
int pre(int val){
    int x,y;
    split(root,val-1,x,y);
    int res=Kth(x,sz[x]);
    root=merge(x,y);
    return res;
}
int nxt(int val){
    int x,y;
    split(root,val,x,y);
    int res=Kth(y,1);
    root=merge(x,y);
    return res;
}
int main(){
    srand(time(NULL));

    cin>>n;
    for(int i=1,op,x;i<=n;i++){
        scanf("%d%d",&op,&x);
        if(op==1){
            insert(x);
        }else if(op==2){
            del(x);
        }else if(op==3){
            printf("%d\n",Rank(x));
        }else if(op==4){
            printf("%d\n",Kth(root,x));
        }else if(op==5){
            printf("%d\n",pre(x));
        }else if(op==6){
            printf("%d\n",nxt(x));
        }
    }
    return 0;
}

可持久化无旋treap

代码

#include<bits/stdc++.h>
#define debug(x) cerr<<"\tDEBUG: "<<#x<<" = "<<(x)<<endl
#define debug2(a,x) cerr<<#a<<"\tDEBUG: "<<#x<<" = "<<(x)<<endl
using namespace std;
const int maxn=5e5+100,maxm=maxn*50,P=998244353;
bool cur1;
int n;
int tot,rt[maxn],son[maxm][2],sz[maxm],val[maxm],rnd[maxm];
int newnode(int x){
    val[++tot]=x;
    rnd[tot]=rand();
    sz[tot]=1;
    return tot;
}
int copy(int p){
    val[++tot]=val[p];
    sz[tot]=sz[p];
    rnd[tot]=rand();
    son[tot][0]=son[p][0];
    son[tot][1]=son[p][1];
    return tot;
}
void up(int p){
    sz[p]=sz[son[p][0]]+sz[son[p][1]]+1;
}
int merge(int a,int b){
    if(!a||!b)return a|b;
    if(rnd[a]<rnd[b]){
        int p=copy(a);
        son[p][1]=merge(son[a][1],b);
        up(p);
        return p;
    }else {
        int p=copy(b);
        son[p][0]=merge(a,son[b][0]);
        up(p);
        return p;
    }
}
void split(int now,int K,int &x,int &y){
    if(!now){
        x=y=0;
        return;
    }
//  puts("!@#");
    int p=copy(now);
    if(val[now]<=K){
        x=p;
        split(son[p][1],K,son[p][1],y);
        up(p);
    }else {
        y=p;
        split(son[p][0],K,x,son[p][0]);
        up(p);
    }
}
int Kth(int rt,int K){
    int u=rt;
    while(233){
        if(sz[son[u][0]]>=K)u=son[u][0];
        else if(sz[son[u][0]]+1==K)return val[u];
        else K-=sz[son[u][0]]+1,u=son[u][1];
    }
}
int pre(int &rt,int val){
    int x,y;
    split(rt,val-1,x,y);
    int res=Kth(x,sz[x]);
    rt=merge(x,y);
    return res;
}
int nxt(int &rt,int val){
    int x,y;
    split(rt,val,x,y);
    int res=Kth(y,1);
    rt=merge(x,y);
    return res;
}
void del(int &rt,int val){
    int x,y,z;
    split(rt,val,y,z);
    split(y,val-1,x,y);
    y=merge(son[y][0],son[y][1]);
    rt=merge(x,merge(y,z));
}
void insert(int &rt,int val){
    int x,y;
    split(rt,val,x,y);
    rt=merge(merge(x,newnode(val)),y);
}
int Rank(int &rt,int val){
    int x,y;
    split(rt,val-1,x,y);
    int res=sz[x]+1;
    rt=merge(x,y);
    return res;
}
bool cur2;
int main(){
//  double sz=&cur1-&cur2;
//  cout<<sz/1024<<endl;
//  freopen("data.in","r",stdin);
//  freopen("data.out","w",stdout);
    srand(20190824);
    cin>>n;
    insert(rt[0],-2147483647);
    insert(rt[0],2147483647);
//  debug(sz[rt[0]]);
    for(int i=1,t,op,x;i<=n;i++){
        scanf("%d%d%d",&t,&op,&x);
        rt[i]=rt[t];
        if(op==1){
            insert(rt[i],x);
        }else if(op==2){
            del(rt[i],x);
        }else if(op==3){
            printf("%d\n",Rank(rt[i],x)-1);
        }else if(op==4){
            printf("%d\n",Kth(rt[i],x+1));
        }else if(op==5){
            printf("%d\n",pre(rt[i],x));
        }else if(op==6){
            printf("%d\n",nxt(rt[i],x));
        }
    }
    return 0;
}