题解：P5062 [Ynoi Easy Round 2014] 在太阳西斜的这个世界里

· · 题解

本来是系列的第一道题，但是等到现在才写是因为这个题面太令人望而生畏了。

通过模拟红黑树过程，我们可以发现插入一个值的旋转次数不超过 2 次，对应着情况 3，4。

显然我们要在黑点处讨论旋转次数贡献，总的旋转次数则是所有黑点贡献的和。

贡献的形式即是这个黑点的儿子为一红一黑，且红点的儿子变为了红色。

因为红点的儿子必为黑点，所以我们只需在 pushup 的时候同时维护黑点变为红点的方案数。黑变红则来源于这个黑点的两个儿子都为红色，且黑点的孙子变为了红色，这里就容易转移了。

如果是整个值域的查询，维护贡献的子树和就好了。

对于区间 [1,x] 的查询，我们需要先找到 x 插入的位置，再从当前位置往上 pushup，但是要仅保留根链与根链的左子树的贡献。查询完后再从底层重新进行 pushup 就好了。

实现时需要维护当前结点所表示的值域区间，方便计算空结点贡献。可以发现 rotate 操作时只有 2 个结点所表示的区间会发生变化。

所以的确是个 3 分？，但是我实现能力太弱了，要调很久……