左偏树是一种支持合并的二叉堆。记 \(dis_u\) 表示点 \(u\) 到最近的叶子的距离，那么左偏树时刻满足 \(dis_u=dis_{rc}+1\land dis_lc\geq dis_rc\) 且它的深度是严格 \(O(\log n)\)。
template<int N,class T> struct leftree{
int ch[N+10][2],dis[N+10],tot; T val[N+10];
leftree():tot(0){dis[0]=-1;}
int newnode(T x){int p=++tot;return val[p]=x,ch[p][0]=ch[p][1]=0,dis[p]=0,p;}
int merge(int p,int q){
if(!p||!q) return p+q;
if(val[p].first-val[q].first>=eps) swap(p,q);
int u=newnode(val[p]);
ch[u][0]=ch[p][0],ch[u][1]=merge(ch[p][1],q);
if(dis[ch[u][0]]<dis[ch[u][1]]) swap(ch[u][0],ch[u][1]);
dis[u]=dis[ch[u][1]]+1;
return u;
}
};