2018-team4-modules-非旋Treap

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
#define L a[t].l
#define R a[t].r
#define F fa[t]
typedef pair<int,int> pii; 
void get(int &x,int &y,pii t){x=t.first,y=t.second;}

//merge，返回值为合并后的根
//若其中一个为空树直接返回，否则递归
int mer(int x,int y){
    return x==0||y==0?x+y:a[y].k>a[x].k?
    (a[x].r=mer(a[x].r,y),up(x),x):
    (a[y].l=mer(x,a[y].l),up(y),y);
}

//从上向下分裂，返回值为分裂后的两个根 
pii spl(int t,int k){
    if (!k) return pii(t,0);
    if (k==a[t].sz) return pii(0,t);
    int p=k-a[R].sz-1; return p>=0?
    (get(p,L,spl(L,p)),up(t),pii(p,t)):
    (get(R,p,spl(R,k)),up(t),pii(t,p));
}

//自下向上分裂，要多维护一个fa数组 
//要多维护个fa数组，split的时候要清fa
pii spl(int t){
    int l=L,r=R,tp=t;
    for (;F;t=F) a[F].l==t?
        r=fa[a[F].l=r]=F:
        l=fa[a[F].r=l]=F;
    t=tp,L=R=F=fa[l]=fa[r]=0;
    return pii(l,r);
}

}}}

#define L a[t].l
#define R a[t].r
#define F fa[t]
typedef pair<int,int> pii; 
void get(int &x,int &y,pii t){x=t.first,y=t.second;}
//merge，返回值为合并后的根
//若其中一个为空树直接返回，否则递归
int mer(int x,int y){
    return x==0||y==0?x+y:a[y].k>a[x].k?
    (a[x].r=mer(a[x].r,y),up(x),x):
    (a[y].l=mer(x,a[y].l),up(y),y);
}
//从上向下分裂，返回值为分裂后的两个根 
pii spl(int t,int k){
    if (!k) return pii(t,0);
    if (k==a[t].sz) return pii(0,t);
    int p=k-a[R].sz-1; return p>=0?
    (get(p,L,spl(L,p)),up(t),pii(p,t)):
    (get(R,p,spl(R,k)),up(t),pii(t,p));
}
//自下向上分裂，要多维护一个fa数组 
//要多维护个fa数组，split的时候要清fa
pii spl(int t){
    int l=L,r=R,tp=t;
    for (;F;t=F) a[F].l==t?
        r=fa[a[F].l=r]=F:
        l=fa[a[F].r=l]=F;
    t=tp,L=R=F=fa[l]=fa[r]=0;
    return pii(l,r);
}