定义定义定义！
感觉理解分治的时候挺好用的，也就是我常说的推锅下去。
函数式线段树（主席树）
函数式平衡树 (fhq_treap)
以及若干东西，你都可以定义下去。
本质上是一个映射，对于你输入的东西映射，再通过定义去得到最终结果。
https://max.book118.com/html/2016/0304/36834109.shtm
考虑一个东西
fhq_treap 需要满足 \(val_1\) 满足 BST 性质，\(val_2\) 满足 heap 性质，你可以认为 \(val_2\) 是为了让 fhq_treap 平衡才加进去的一个随机权值。
考虑定义若干函数：
pair<int,int> split(x,k) 表示将 \(x\) 这棵树分裂成两棵 treap，满足第一棵 treap 的 \(val_1\) 的最大值小于等于 \(k\)，第二棵 treap 的最小值大于 \(k\)。
考虑我仅仅只需要满足当前该咋做，接着推锅下去即可。
if(val1(x)<=k) {
a=x; auto qwq=split(x.rs,k);
a.rs=qwq.first;
b=qwq.second;
} else { //则把 x 的 rs 都给 b，然后考虑 ls 即可。
b=x; auto qwq=split(x.ls,k);
a=qwq.first;
b.ls=qwq.second;
}
return mp(a,b);
注意看我每一步只做了什么？当前是咋样的，通过子问题得到的结果来保证当前的正确性。因为只会跑 O(树高) 次，然后你 fhq_treap 保持平衡，所以复杂度就是对的。
merge(x,y) 合并 x,y 两棵树。需要注意，建议你把所有的树都看成外向树，也就是你实际上合并的是子树 x，子树 y，它可能原先所在的树并不以它为根。不过这没关系，因为我们定义就是以它为根，既然最开始的时候满足，那么我们只需要接下来每一步都满足即可。
我们限定 x,y 满足 \(\max val_1 T(x)<\min val_1 T(y)\)，所以你合并的时候 \(val_1\) 的性质是很好满足的，所以你只需要满足 heap 的性质。
若我们钦定合并完是以当前的 y 为根（根据 \(val_2\) 大小钦定，即满足堆的性质），因为你要么 x 为根，要么 y 为根，因为我们不带旋转操作，下面的点没办法旋上来。
push_down(y); push_down(x);
y.ls=merge(x,y.ls);
return y;
复杂度显然还是树高次。
因为你若以 \(y\) 为根，显然其 rs 都是直接保留的，因为你 \(x\) 不可能能插到其 rs 的。那么你只需要考虑 ls 对应的树，显然为 x,y.ls 合并起来的，注意顺序不能颠倒！需要满足定义！
然后可持久化是很好做的，具体的，你只需要根据定义来做即可。即类主席树一样定义若干个版本的树，然后你显然是要根据定义来继承旧版本信息的。
你就直接定义 split 为分裂出 2 棵新 treap，而不更改原先节点的外向边，merge 也是合并为新 treap，不更改原先 2 棵树的本身结构。
因为都是外向边，所以认子不认父，一个点可以有多个父亲，这也是为啥复杂度正确。
标签：重学,定义,val,编程,treap,满足,为根,DS,ls From： https://www.cnblogs.com/xugangfan/p/16987040.html