平衡树哲学-个人总结
i207M
2018-11-07 17:44:47
~~与“线段树哲学”照应~~
平衡树还是Splay好啊，能干的事多；
**平衡树pushup的时候一定注意空儿子的情况！**
# Treap
注意删除时要pushup；递归进入的时候分清楚左右儿子；
# Splay
重点说一下NOI2005维护序列的注意事项吧：
1. 因为我的标记哲学很特殊，所以pushup之前要pushdown自己和儿子
2. 在把两个Splay合并时，记得ch和fa要同时改。
3. 这道题有tot=0的情况。
# fhqTreap
如果写的是可重的fhq，记得gatrank要特殊写；
正常fhq：
```cpp
void ins(int v)
{
int a,b,x;
split(rt,v,a,b);
split(a,v-1,a,x);
if(x)
{
++cnt[x];
up(x);
rt=merg(merg(a,x),b);
}
else rt=merg(merg(a,cre(v)),b);
}
void del(int v)
{
int a,b,x;
split(rt,v,a,b);
split(a,v-1,a,x);
if(cnt[x]>1)
{
--cnt[x];
up(x);
rt=merg(merg(a,x),b);
}
else
{
x=merg(ls,rs);
rt=merg(merg(a,x),b);
}
}
```