下图是这个回答中的代码
原代码:
int merge(int x,int y)
{
return (!x||!y)
?( (x)?(x):(y) )
:( (rand()%(tr[x].siz+tr[y].siz)<tr[x].siz)
?( tr[++tot]=tr[x], x=tot, tr[x].ch[1]=merge(tr[x].ch[1],y), update(x), x)
:( tr[++tot]=tr[y], y=tot, tr[y].ch[0]=merge(x,tr[y].ch[0]), update(y), y)
);
}
等价代码:
int merge(int x,int y)
{
if(x==0||y==0)
{
if(x!=0) return x;
else return y;
}
else
{
if( rand()%(tr[x].siz+tr[y].siz) < tr[x].siz )
{
tr[++tot]=tr[x];
x=tot;
tr[x].ch[1]=merge( tr[x].ch[1] , y );
update(x);
return x;
}
else
{
tr[++tot]=tr[y];
y=tot;
tr[y].ch[0]=merge( x , tr[y].ch[0] );
update(y);
return y;
}
}
}
原代码:
void split(int x,int e)
{
(!x)
?(l=r=0)
:(tr[++tot]=tr[x],x=tot,( (tr[tr[x].ch[0]].siz>=e)
?(split(tr[x].ch[0] , e), tr[x].ch[0]=r, r=x)
:(split(tr[x].ch[1] , e-tr[tr[x].ch[0]].siz-1), tr[x].ch[1]=l , l=x)
),update(x)
);
}
等价代码:
void split(int x,int e)
{
if(x==0)
{
l=r=0;
}
else
{
tr[++tot]=tr[x];
x=tot;
if( tr[tr[x].ch[0]].siz >= e)
{
split( tr[x].ch[0] , e );
tr[x].ch[0]=r;
r=x;
}
else
{
split( tr[x].ch[1] , e-tr[tr[x].ch[0]].siz-1 );
tr[x].ch[1]=l;
l=x;
}
update(x);
}
}