int merge(int x, int y){
	if(!x || !y) return x+y;
	if(d[x]>d[y]) swap(x, y);
	int l, r;
	spt(y, val[x], l, r);//分裂
	son[x][0]=merge(son[x][0], l), son[x][1]=merge(son[x][1], r);
	push_up(x);
	return x;
}

大致思路：设树根为 $x$，另一颗树树根为 $y$ ，满足 $d_x<d_y$，然后将 $y$ 按 $val_x$ 分裂，分别到 $x$ 的左右子树再进行合并。，保证任意两个数的 $val$ 都不相同，$d$ 数组是随机数。平均时间复杂度应该为 $O(\log^2 n)$,可最坏时间复杂度应该为多少？窝太菜了，不会证。。。