粗略的翻了一下题解区 FHQ - Treap 的思路，大概（？）没有这么实现的 Insert，也可能是常数比较大。

令 $k$ 为 $s$ 在树上的排名。

思路大概是：

• 按照 $s$ 分裂为 $[1, k - 1], [k, n]$，进而提取出 $[1, k - 1], [k, k], [k + 1, n]$。
• 合并为 $[1, k - 1] \cap [k + 1, n]$
• 令 $k' = k + t$
• 将 $[1, k - 1] \cap [k + 1, n]$ 按照 $k'$ 分裂为 $[1, k' - 1], [k', n]$，进而合并为 $[1, k' - 1] \cap [k, k] \cap [k' + 1, n]=[1, n]$

可能看着有点抽象，但是大概就分割两段之后把点取出来，合起来再把原段按照新位置分成点要插到的两段，之后按顺序合并即可。

代码是这样的

inline void Insert(int s, int t) {
	if(t == 0) return ;
	int x, y, P, z, k = get_rk(pos[s]);
	split_sz(root, k - 1, x, y), split_sz(y, 1, P, z), k += t;
	root = merge(x, z); split_sz(root, k - 1, x, y), root = merge(merge(x, P), y);
	return ;
}

常数比较的大（），毕竟用了很多次的 split_sz 的操作，这么多 $\log$ 是不是要根号了