rt
merge
int merge(int rt1,int rt2){
if(!rt1||!rt2) return rt1|rt2;
if(rk[rt1]<rk[rt2]){
pushdown(rt1);
son[rt][1]=merge(son[rt][1],rt2);
pushup(rt1);
return rt1;
}
else{
pushdown(rt2);
son[rt2][0]=merge(rt1,son[rt2][0]);
pushup(rt2);
return rt2;
}
}
spilt
pair<int,int> spilt<int rt,int y>{
pair<int,int> ans;
if(rt==0){
ans.first=ans.second=0;
return ans;
}
if(sz[rt]>=y){
ans=spilt(son[rt][0],y);
son[rt][0]=ans.second;
ans.second=rt;
}
else{
ans=spilt(son[rt][1],y);
son[rt][1]=ans.first;
ans.first=rt;
}
pushup(rt);
return ans;
}
newnode
int newnode(int x){
tot++;
key[tot]=x;
sz[tot]=1;
rk[tot]=rank();
return tot;
}
find
int find(int k,int rt=top){
pushdown(rt);
if(sz[son[rt][0]]>=k)
return find(k,son[rt][0]);
k-=sz[son[rt][0]];
if(k==1) return key[rt];
k--;
return find(k,son[rt][1]);
}