FHQ 滿足 \(val_{{ls}_{u}} \le val_u \le val_{{rs}_{u}}\)

對于每一個節點 \(u\) , 我們維護 \(sz_u\) 和 \(val_u\) 以及 \(rd_u\) (隨機的 \(key\) ) .

1. 按 \(val\) 分裂：

考慮維護兩個指針，分別代表兩課樹，先判斷 \(val_u\) 的大小與 \(v\) 的關系，然后向對應方向分裂。
具體地，如果 $val_u < v $ 那么把 \(u,ls_u\) 劃入 \(x\) ,向\(rs_u\) 遞歸；相反，就向 \(ls_u\) 遞歸。

inline void spl(int u,int v,int &x,int &y){
	if(!u) return x=y=0,void();
	if(t[u].val<=v) spl(t[u].r,v,t[x=u].r,y);
	else spl(t[u].l,v,x,t[y=u].l);
	up(u);
}

2.按排名分裂：

類比按 \(val\) 分裂，對于 \(sz_{ls_u}\) 分討即可。

3.合并

需要滿足 \(\forall u \in x , v \in y 有 val_u \le val_v\)。
否則，我們只能進行啟發式合并 \(O(log^2 n)\).

既然我們確定了 \(val\) 的關系，就只要考慮 \(key\) 的大小. 按照 \(key\) 的大小確定根節點，遞歸分討即可。

inline int merge(int x,int y){
	if(!x || !y) return x + y;
	if(t[x].rd<t[y].rd) return t[y].l=merge(x,t[y].l),up(y),y;
	return t[x].r=merge(t[x].r,y),up(x),x;
}

對于其他找 \(rank,pre，kth\) 等操作：直接在樹上找或者利用分裂合并找答案。

一般地，在實現中，寫 \(val < v\) 而不是 \(val \le v\).