【Ynoi2014】在太阳西斜的这个世界里

foreverlasting · 2019-07-30 20:03:52 · 题解

推销博客

一道需要分类讨论的平衡树好题。 <!--more-->

首先你要先研究一下什么时候红黑树会旋转。

这种情况是一个结点为黑色，而且它的儿子一红一黑，并它的红儿子拥有红儿子的时候，进行旋转操作。至于这里是单旋还是双旋，其实是像splay一样，看三点是否共线，即爷爷，红爸爸，红儿子是否共线。

除了旋转以外，我们还需要思考直接更改颜色的情况。

这种情况是一个黑爸爸，两个红儿子，有个红孙子，那么就只用把黑爸爸变成红爸爸，红儿子变成黑儿子，然后递归操作即可。

于是每次插入新点的时候，自底向上地利用红黑树可维护的信息更新答案。

考虑维护什么信息。

黑点：需要知道在子树内插入几个点才能使黑点变色。

红点：需要知道左右孩子分别变红的方案数。

任意点：需要知道子树内插入一个点需要旋转的次数。

然后通过这些信息在插入一个点的时候将其旋到根时进行计算，注意一个trick，就是你可以复制一棵原有的树直接插入一个点进行计算。这样代码写起来会简单很多。

代码，就不给了吧QAQ（反正我没实力也就不会写了）

似乎没人看懂我写了啥，那我重写一遍。

点x为红时，ans[x]=ans[ls]+ans[rs]

点x为黑时，ans[x]+=ans[ls]+ans[rs]。如果x拥有黑红儿子的时候，可能红儿子会翻身做主人。左右谁为黑儿子的计算方式类似，这里只阐述其中的一种。

假设当前ls为黑儿子。ls造反需要的是rs的帮助，即rs为红，rs的儿子中也有红色才行。由于rs已经是红色了，所以它的儿子不应该会有红，但有了红色出现了不满足红黑树的情况，是由insert的时候改变而来的，因此要记录一个黑点变红的期望，并且记录一个红点儿子变红的期望。这样我们再考虑此时rs的贡献，我们思考单旋和双旋的情况，可以得知的是rs的贡献显然是rs的左儿子变红的期望\ast 2+rs的右儿子变红的期望。