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

 现在我的梦想实现了 也留下了美好的回忆 可以说没有任何遗憾了吧  今天真是多谢你了 让我体验了许多美好 这全都是托你的福 我留下了如同美梦一般的回忆 不过时间到了 最后我还想拜托你一件事  希望你可以把我忘掉

珂朵莉需要维护一棵初始为空的红黑树，进行 $n$ 次操作。 对于重复的整数，我们认为插入时间晚的一个更小。 操作有两类： * $op=1$：在红黑树上插入一个整数$x$。 * $op=2$：给出 $x$，询问从 $1$ 到 $x$ 的整数中等概率选取一个插入到红黑树上，造成的旋转次数的期望值，方便起见，你只要输出 期望值$\times x$，（可以证明这是一个整数）。

无

无

红黑树是一棵二叉查找树，每个点有颜色（红/黑）。 每次执行插入操作时，新插入的点为红色，操作方式和普通二叉查找树相同。 如果出现两个红色的点互为父子，如图进行调整（操作是左右对称的，对称操作在图中不再重复列出；黑色三角形表示空或以黑色点为根的子树），调整可能需要连续进行多次。 调整完毕后，把根设为黑色。  Idea：ccz181078，Solution：ccz181078，Code：ccz181078，Data：ccz181078 $1\leq n\leq 2\times 10^5$，$1\leq op\leq 2$，$1\leq x\leq 10^8$。