自动搬运

查看原文

来自洛谷，原作者为

	foreverlasting 果然，失去别人远比自己离去更加令人恐惧。

搬运于2025-08-24 22:06:42，当前版本为作者最后更新于2019-07-30 20:03:52，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

推销博客

一道需要分类讨论的平衡树好题。

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

这种情况是一个结点为黑色，而且它的儿子一红一黑，并它的红儿子拥有红儿子的时候，进行旋转操作。至于这里是单旋还是双旋，其实是像$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$的右儿子变红的期望。

$rs$为黑类似。

于是就能维护变色的情况，旋转情况类似。

最后再考虑插入一个值域$[1,p]$的点旋转次数的期望如何统计。

你考虑找到这个点所应该存在的空位，然后自底向上地把这个点到根的路径上的答案进行统计。统计的时候你就不断缩小这个值域区间，再利用之前所得到的信息，就可以方便地计算答案了。

复杂度$O(nlogn)$。