平衡树：treap学习笔记（2）

上一次写了旋转的treap（代码非常简单。

这次我们来写无旋的treap。这个treap没有旋转操作。

有两个基本操作：合并、分裂。

插入和删除时都使用到了这两个操作，感觉很妙呀qaq。

具体的解释详见：https://wenku.baidu.com/view/09fbf8147c1cfad6195fa7f0.html；

还有zcy的代码：https://www.cnblogs.com/zcysky/p/6876646.html

还有http://blog.csdn.net/wyj_jenny/article/details/78559603；

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair

typedef pair<int,int>par;
const int MAXN=;
const int INF=;

int rt=,cnt=;

struct treap{
    int lson[MAXN],rson[MAXN],size[MAXN],prio[MAXN],w[MAXN];
    inline void pushup(int p){size[p]=size[lson[p]]+size[rson[p]]+;}
    par split(int p,int x){
        if(!x)return mp(,p);
        int l=lson[p],r=rson[p];
        if(x<=size[l]){//下面千万别打错。
            par tem=split(l,x);
            lson[p]=tem.second;pushup(p);return mp(tem.first,p);
        }
        par tem=split(r,x-size[l]-);
        rson[p]=tem.first;pushup(p);return mp(p,tem.second);
    }
    int merge(int x,int y){
        if(!x){
            pushup(y);return y;
        }
        if（!y){
            pushup(x);return x;
        }
        if(prio[x]<prio[y]){
            rson[x]=merge(rson[x],y);pushup(x);return x;
        }
        else {
            lson[y]=merge(x,lson[y]);pushup(y);return y;
        }
    }
    int queryrank(int p,int x){
        int ans=,tem=INF;
        while(p){//p的转换，顺序别打反。
            if(x==w[p])tem=min(tem,ans+size[lson[p]]+);
            if(x>w[p])ans+=size[lson[p]]+,p=rson[p];
            else p=lson[p];
        }
        return tem==INF?ans:tem;
    }
    void insert(int x){
        int k=queryrank(rt,x);par tem=split(rt,k);
        w[++cnt]=x;prio[cnt]=rand();size[cnt]=;
        rt=merge(tem.first,cnt);rt=merge(rt,tem.second);
    }
    void del(int x){
        int k=queryrank(rt,x);par t1=split(rt,k),t2=split(t1.first,k-);
        rt=merge(t2.first,t1.second);
    }
    int findnum(int p,int x){
        for(;;){
            if(x==size[lson[p]]+)return w[p];
            if(x<size[lson[p]]+)p=lson[p];
            else x=x-size[lson[p]]-,p=rson[p];
        }
    }
    int findpre(int p,int x){
        int ans=-INF;
        while(p){
            if(x>w[p]){
                ans=max(ans,w[p]);
                p=rson[p];
            }
            else p=lson[p];
        }
        return ans;
    }
    int findsub(int p,int x){
        int ans=INF;
        while(p){
            if(x<w[p]){
                ans=min(ans,w[p]);
                p=lson[p];
            }
            else p=rson[p];
        }
        return ans;
    }
}treap;

int main(){
    int n,opt,x;
    scanf("%d",&n);srand();
    for(int i=;i<=n;i++){
        scanf("%d%d",&opt,&x); 
        if(opt==)treap.insert(x);
        if(opt==)treap.del(x);
        if(opt==)printf("%d\n",treap.queryrank(rt,x));
        if(opt==)printf("%d\n",treap.findnum(rt,x));
        if(opt==)printf("%d\n",treap.findpre(rt,x));
        if(opt==)printf("%d\n",treap.findsub(rt,x));
    }
    return ;
}