upd：暴力推平的复杂度分数写反了。
调了 10h 的 FHQ-Treap 调疯了，然后直接加入邪修（
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
替罪羊树是一个比较暴力的平衡树。
首先我们复习一下普通二叉树是怎么加入元素的：
* 如果已经遍历到不存在的节点了，就新开一个节点。
* 如果当前节点的值恰好是要修改的值，就修改。
* 否则如果要修改的值小于当前节点的值，就往左子树搜。
* 否则往右子树搜。
* 然后 push_up 合并左右子树及当前节点的信息。
这样子会有什么问题呢？
注意到出题人可能会构造数据，让你建出一个十分不平衡的二叉树，然后就炸了。显然单次查询最坏可以卡到 O(n)O(n)O(n)。
那不平衡怎么办呢？把它弄平衡呗。
我们可以在修改的时候判断当前节点，如果发现这个节点不太平衡了，就直接暴力把这个子树重构成一个最平衡的完全二叉树。
判断一个节点不平衡的方法有很多种，我这里用的是比较子树节点个数。
定义 sizeu\text{size}_usizeu 为节点 uuu 的子树节点数量，如果 sizesonu≥α×sizeu\text{size}_{\text{son}_u}\ge \alpha\times \text{size}_usizesonu ≥α×sizeu ，那么就将他看做不平衡，其中 α\alphaα 是一个 (0.5,1)(0.5,1)(0.5,1) 的数。
这么做为什么是对的呢？
首先考虑查询复杂度。
由于某儿子的 size\text{size}size 大于等于父亲的 size\text{size}size 的 α\alphaα 倍就会被重构，所以在每次操作后一定满足两个子树的 size\text{size}size 小于父亲的 size×α\text{size}\times \alphasize×α。而查询就是递归到 size≤1\text{size}\le 1size≤1 的点，所以时间复杂度是 O(log1αn)O(\log_{\frac{1}{\alpha}} n)O(logα1 n) 的。
然后看看暴力重构复杂度。
假设一个节点的子树当前处于完全平衡状态（sizesonu=0.5sizeu\text{size}_{\text{son}_u}=0.5\text{size}_usizesonu =0.5sizeu ），则解方程可得至少增加 2α−11−αsizeu\frac{2\alpha-1}{1-\alpha}\text{size}_u1−α2α−1 sizeu 个节点才能使得它被 O(sizeu)O(\text{size}_u)O(sizeu ) 重构，然后又处于平衡状态。均摊时间复杂度为 O(1−α2α−1)O(\frac{1-\alpha}{2\alpha-1})O(2α−11−α )。
所以只要 α\alphaα 不设得太离谱这个复杂度就是 O(logn)O(\log n)O(logn) 的。
直接贴代码。
