提交记录

ll mrg(ll L, ll R) {
	if (!L || !R) {
		return L + R;
	}
	if (node[L].val <= node[R].val) {
		node[L].r = mrg(node[L].r, R);
		node[node[L].r].p = L;
		if (node[node[L].r].d > node[node[L].l].d) {
			swap(node[L].l, node[L].r);
		}
		node[L].d = node[node[L].r].d + 1;
		return L;
	} else {
		node[R].l = mrg(L, node[R].l);
		node[node[R].l].p = R;
		if (node[node[R].l].d < node[node[R].r].d) {
			swap(node[R].l, node[R].r);
		}
		node[R].d = node[node[R].r].d + 1;
		return R;
	}
}

树是左偏的，但是在合并的时候有概率访问到左子，复杂度应该是退化了的，如果树是向左的链就是 $\Omicron(qn)$ 的了。但是交上去最高的点也就 20ms 不到？这种写法怎么卡，至少在 $n=q=10^6$ 的时候卡出 1s？