普通平衡树

很久以前，我很抗拒使用平衡树。
但是这现在是 8 级算法，我不得不学之。
FHQ-Treap
核心只有两个操作 split 和 merge。
考虑像 Treap 一样每个点打上 rand，使得其满足是 rnd 的小根堆。
然后考虑分裂。
考虑每次对于值归类 <= 的归在 \(lt\)，其他归在 \(rt\)。
考虑每次归入 \(lt\) 一个数，那么其他的就是考虑填 lt 的右儿子。
那么同理，归入 \(rt\) 一个数，那么就是考虑填 rt 的左儿子。
按照一条链分裂后，记得 pushup。
那 merge 就考虑 \(lt, rt\) 此时已经满足了 \(max_{lt} \leq min_{rt}\)，我们每次要满足小根堆。
所以如果 \(rnd_x \leq rnd_y\) 那么把 \(y\) 插到 \(x\) 的右儿子。否则把 \(x\) 插入到 \(y\) 的左儿子，pushup 后 return 根即可。

void split (int x, int k, int & lt, int & rt) {
	if (!x) { lt = rt = 0; return ; }
	if (tr[x].v <= k) { lt = x; split(rc(x), k, rc(x), rt); }
	else { rt = x; split(lc(x), k, lt, lc(x));}
	pushup(x);
}
void split (int x, int k, int &lt, int & rt) {
	if (!x)  { lt = rt = 0; return ; }
    pushdown(x);
	if (sz[lc[x]] >= k) {
		rt = x;
		split(lc[x], k, lt, lc[x]);
	} else {
		lt = x;
		split(rc[x], k - sz[lc[x]] - 1, rc[x], rt);
	}
	pushup(x);
}
int merge (int x, int y) {
	if (!x || !y) return x | y;
    pushdown(x), pushdown(y);
	if (rnd[x] <= rnd[y]) {
		rc[x] = merge(rc[x], y), pushup(x); 
		return x;
	} else {
		lc[y] = merge(x, lc[y]), pushup(y); 
		return y;
	}
}

如果有 \(reverse\)
其实主要是为了做文本编辑器写的（）。