\(\rm fhqTreap\) 学习笔记&做题记录
发大电部分
我是 \(\rm fhqTreap\) 批
众所周知， \(\rm fhqTreap\) 可以部分（或者完全？）替代splay的区间功能，而且写起来又方便，所以去tm的splay。
正片
\(\rm fhqTreap\) 又称无旋 \(\rm Treap\)，是 \(\rm Treap\) 的一种，由 \(\rm fhq\) 神犇发明。
顾名思义， \(\rm fhqTreap\) 与旋转 \(\rm Treap\) 相比不需要旋转操作。
好像有一种说法， \(\rm fhqTreap\) 的 \(\rm TreeHeap\) 中的 \(\rm Heap\) 是可并堆？
结点信息
和旋转 \(\rm Treap\) 完全相同。
基本操作
\(\rm fhqTreap\) 的基本操作为分裂 \(\rm split\) 和合并 \(\rm merge\)。
split
这个操作要求传4个参数：p,s,&x,&y
p：要分裂的树的树根x：分裂后左树的树根y：分裂后右树的树根s：x树的大小（也可以是x树的最大值，可以根据实际情况改变）
功能
把整棵树按照你要求的方式分成两半。
实现
我们可以很轻松的判断根节点应该在 x 树或者 y 树。
如果根节点在 x 树，那么说明整个根左树在 x 树且右子树有一部分在 x 树，那么递归到右子树；反之，说明整个根右树在 y 树且左子树右一部分在 y 树，递归到右子树。
//split by size
void split(int p,int s,int& x,int& y){
if(!p)return void(x=y=0);
pushdown(p);
int rk=t[ls(p)].siz+1;
if(rk<=s){
x=p;
split(rs(p),s-rk,rs(p),y);
}
else{
y=p;
split(ls(p),s,x,ls(p));
}
pushup(p);
}
//split by value
void split(int p,int s,int &x,int &y){
if(!p)return void(x=y=0);
pushdown(p);
if(s>=t[p].val){
x=p;
split(rs(p),s,rs(x),y);
}
else{
y=p;
split(ls(p),s,x,ls(y));
}
pushup(p);
}
merge
这个操作要求传2个参数：x,y。
x,y 是两棵 \(\rm fhqTreap\) 的根节点，保证 x 树整体小于 y 树。
功能
把两颗 \(\rm fhqTreap\) 合并，返回合并后树的根结点编号。
实现
比较两棵树根的 \(\rm priority\)，按照 \(\rm Treap\) 优先级的特殊性质决定谁是新根，并递归到子树继续合并。
int merge(int x,int y){
if(!x||!y)return x+y;
if(t[x].pri<t[y].pri){
pushdown(x);
rs(x)=merge(rs(x),y);
return pushup(x),x;
}
pushdown(y);
ls(y)=merge(x,ls(y));
return pushup(y),y;
}
时间复杂度分析
操作的次数取决于树高，而 \(\rm Treap\) 的期望树高为 \(\log n\)，因此单次 \(\rm split\) 和 \(\rm merge\) 时间复杂度均为 \({\rm{O}}(\log n)\)。
实用操作
基本套路是把树分裂成 \([1..l-1],[l..r],[r+1..n]\) 三个部分然后对中间部分搞事情最后合并回去。
插入一个/多个值
把原树分裂成小于插入值部分和大于插入值部分，新建一些结点并用笛卡尔树建树法建成一颗 \(\rm fhqTreap\) 并与原来分裂出来的两颗树合并。（\(\rm Treap\) 的本质是一颗笛卡尔树）
删除一个/多个值
把原树分裂成小于插入值部分和大于插入值部分和被删除值本身，把这个中间部分删除并合并原来两树即可。
上述操作单次复杂度为 \(m + \log n\)，其中 \(m\) 为单次操作元素个数，\(n\) 为树的大小。
区间反转/加/乘/各种奇怪的东西
树分成三部分，中间打懒标记，合并回去。
时间复杂度 \(\log n\)。
查名次/K大/前驱/后继
分裂一下自己就出来了。
K大还有点bug，建议与旋转 \(\rm Treap\) 同款。
优点
好写！
能分裂！其实好像旋转 \(\rm Treap\) 也能分裂，方式是强行把要旋转的值旋转到根然后强行分裂
不用记父亲！
能持久化！splay是什么寄吧
缺点
常数比较大。但是splay常数也大，所以splay还是歌姬吧！
例题
P3391文艺平衡树
给序列 \(1,2,\dots,n\)，进行 \(m\) 次操作，每次翻转一个区间，输出最后的数列，\(n,m\le 10^5\)
裸题。直接上区间翻转懒标记就好。时间复杂度线性对数。
P4146序列终结者
长度 \(n\) 序列，\(m\) 次操作，区间加区间反转区间最大值，\(n \le 5\times 10^4,m \le 10^5\)
继续裸题。直接上区间翻转和加和懒标记。时间复杂度线性对数。
P3224永无乡
初始 \(n\) 个点权结点有一些边相连，\(q\) 次操作包含连接两个结点和询问所在连通块点权 \(k\) 小。\(n \le 10^5,q \le 3\times 10^5\)
并查集+启发式合并平衡树即可。有点细节，注意空间利用。
时间复杂度线性乘对数的平方。
（最开始写合并写挂了，我菜死了QwQ）
P3278多项式的运算
P4036火星人
一个字符串，操作涉及单点修改、单个字符插入、求两个后缀的最长公共前缀。
字符串长度 \(\le 10^5\)，询问操作不超过 \(10^4\) 次。
另一个平衡树裸题，额外再维护一下区间的哈希值就成，询问二分答案即可。
单次修改对数，单次询问对数平方。
标签：10,记录,int,fhqTreap,复杂度,笔记,Treap,rm From： https://www.cnblogs.com/pokefunc/p/17036911.html