非旋Treap入门讲义

#include<bits/stdc++.h>
using namespace std;
inline int gi() {
    register int x=0,op=1,c;
    while(c=getchar(),c<‘0‘||c>‘9‘)if(c==‘-‘)op=-op;
    x=c^48;
    while(c=getchar(),c>=‘0‘&&c<=‘9‘)x=(x<<3)+(x<<1)+(c^48);
    return x*op;
}
struct node {
    int son[2];
    int val, s;
    int v;
    node() {
        son[0] = son[1] = 0;
        s = 0;
        val = rand();
    }
}t[100001];
void push_up(int p) {
    t[p].s = t[t[p].son[0]].s + t[t[p].son[1]].s + 1;
}
void split_v(int p, int v, int &x, int &y) 
{
    if(!p)return void(x = y = 0);
    if(t[p].v>v) 
	{
        y = p;
        split_v(t[p].son[0], v, x, t[p].son[0]);
    }
    else {
        x = p;
        split_v(t[p].son[1], v, t[p].son[1], y);
    }
    push_up(p);
}
void split_k(int p, int k, int &x, int &y) {
    if(!p)return void(x = y = 0);
    if(k <= t[t[p].son[0]].s) {
        y = p;
        split_k(t[p].son[0], k, x, t[p].son[0]);
    }
    else {
        x = p;
        split_k(t[p].son[1], k - t[t[p].son[0]].s - 1, t[p].son[1], y);
    }
    push_up(p);
}
int merge(int x, int y) 
{
    if(! x || ! y)return x + y;
    if(t[x].val < t[y].val) 
    //每个点有个随机优先级 
	{
        t[x].son[1] = merge(t[x].son[1], y);
        //将y与x的右子树合并，再做为x的右子树 
        push_up(x);
        return x;
    }
    else 
	{
        t[y].son[0] = merge(x, t[y].son[0]);
        // 将x与y的左子树合并，再做为y的左子树 
        push_up(y);
        return y;
    }
}
int tot=0;
int new_node(int v) 
{
    t[++tot].v = v;
    t[tot].s=1;
    return tot;
}
int root=0;
int main() {
    srand(time(0));
    int n=gi();
    int op,x;
    int r1,r2;
    while(n--) {
        op=gi(),x=gi();
        switch(op) {
        case 1://插入
            split_v(root,x,root,r1);
            root=merge(root,merge(new_node(x),r1));
            break;
        case 2://删除
            split_v(root,x-1,root,r1);
            split_k(r1,1,r2,r1);
            root=merge(root,r1);
            break;
        case 3://排名
            split_v(root,x-1,root,r1);
            printf("%d\n",t[root].s+1);
            root=merge(root,r1);
            break;
        case 4://k小值
            split_k(root,x-1,root,r1);
            split_k(r1,1,r1,r2);
            printf("%d\n",t[r1].v);
            root=merge(root,merge(r1,r2));
            break;
        case 5://前驱
            split_v(root,x-1,root,r1);
            split_k(root,t[root].s-1,root,r2);
            printf("%d\n",t[r2].v);
            root=merge(root,merge(r2,r1));
            break;
        case 6://后继
            split_v(root,x,root,r1);
            split_k(r1,1,r1,r2);
            printf("%d\n",t[r1].v);
            root=merge(root,merge(r1,r2));
        }
    }
    return 0;
}

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef pair<int,int> pii;
int tot,son[100005][2],c[100005],val[100005],root;
int read()
{
    int x=0,f=1;
    char ch=getchar();
    for(;ch<‘0‘||ch>‘9‘;ch=getchar())if(ch==‘-‘)f=-1;
    for(;ch>=‘0‘&&ch<=‘9‘;ch=getchar())x=x*10+ch-‘0‘;
    return x*f;
}
int random(int lim)
{
    return rand()%lim+1;
}
void updata(int a)
{
    c[a]=c[son[a][0]]+1+c[son[a][1]];
}
int getrank(int v)  //查找权值为v的数字的排名
{
    int res=0;
    for(int x=root;x;)
    {
        if(val[x]<v)   
        //如果当前根结点小于v，则所有v及其左子树均小于v
        {
            res+=c[son[x][0]]+1;
            x=son[x][1];
        }
        else
             x=son[x][0];
    }
    return res+1;
}
pii split(int a,int k)
//从a这个树中分出K个点来，
//这k个点所组成的树的树根做为其左返回值，其它的结点所形成的树做为右返回值
{
    if(c[a]==k)  //如果a这个树正好有k个结点，则直接返回a这个树,右返回值为0
    return make_pair(a,0);
    if(k==0)
    return make_pair(0,a);//左边为空树，右为原来a这个树
    pii tmp;
    if(c[son[a][0]]>=k)//如果左子树结点个数大于等于k
    {
        tmp=split(son[a][0],k);//从左子树中分离
        son[a][0]=tmp.second;//a的左子树只剩下了分离后的结点
        updata(a);//更新a的相关值
        return make_pair(tmp.first,a);//返回分离后的树与从前a树剩下的部分
    }
    else
    {
        tmp=split(son[a][1],k-c[son[a][0]]-1);//减去左子树及根结点
        son[a][1]=tmp.first;
        updata(a);
        return make_pair(a,tmp.second);
    }
}
int merge(int a,int b)
//将根结点编号分为a,b的树进行合并
//此时b树中所有点权值大于a树中的所有点权
{
    if(!a||!b)return a+b;
    if(random(c[a]+c[b])<=c[a])
    {
        son[a][1]=merge(son[a][1],b);//将b做为a的右子树
        updata(a);
        return a;
    }
    else
    {
        son[b][0]=merge(a,son[b][0]);//将a做为b的左子树
        updata(b);
        return b;
    }
}
void insert(int v)
{
    tot++;
    val[tot]=v;
    memset(son[tot],0,sizeof(son[tot]));
    c[tot]=1;
    int x=getrank(v)-1;
    pii tmp=split(root,x);
    //从root中分离出前x个结点,tmp.first为分裂后左树的根结点编号
    //tmp.second为分裂后右根的根结点编号
    root=merge(merge(tmp.first,tot),tmp.second);
    //先将第tot个点与分离出来的左树合并，再与其右树合并
    return;
}
void del(int v) //删除权值为v的数字
{
    int x=getrank(v);
    pii tmp=split(root,x);
    int c=tmp.second;
    tmp=split(tmp.first,x-1);
    root=merge(tmp.first,c);
}
int getval(int a,int k)//查找第k小的数字
{
    if(!k)return 0;
    if(c[son[a][0]]>=k)return getval(son[a][0],k);
    if(c[son[a][0]]+1==k)return a;
    return getval(son[a][1],k-c[son[a][0]]-1);
}
int main()
{
    srand(20020220);
    int n=read();
    for(int i=1;i<=n;i++)
    {
        int mode=read(),x=read();
        if(mode==1)insert(x);
        if(mode==2)del(x);
        if(mode==3)printf("%d\n",getrank(x));
        if(mode==4)printf("%d\n",val[getval(root,x)]);
        if(mode==5)printf("%d\n",val[getval(root,getrank(x)-1)]);
        if(mode==6)printf("%d\n",val[getval(root,getrank(x+1))]);
    }
    return 0;
}