Background

Now my dream has come true, and I have also留下了美好的回忆 (liú xià le měi hǎo de huí yì).
You could say there are no regrets at all.

Thank you so much for today.
You let me experience so many wonderful things.
All of this is thanks to you.
I have memories like a beautiful dream, but the time has come.
Finally, I want to ask you for one more favor.

I hope you can forget me.

Problem Description

Chtholly needs to maintain a red-black tree that is initially empty, and perform $n$ operations.

For duplicate integers, we consider the one inserted later to be smaller.

There are two types of operations:

• $op=1$: Insert an integer $x$ into the red-black tree.
• $op=2$: Given $x$, suppose we choose an integer uniformly at random from $1$ to $x$ and insert it into the red-black tree. Query the expected number of rotations caused by this insertion. For convenience, you only need to output $\text{expected value} \times x$ (it can be proven that this is an integer).

Input Format

The first line contains an integer $n$.

The next $n$ lines each contain two integers $op,x$ separated by a space, representing one operation.

Output Format

For each operation with $op=2$, output one line containing one integer, which is the answer.

10
2 5
1 3
1 4
2 3
2 4
2 5
1 4
2 3
2 4
2 5

0
0
2
3
0
0
0

Hint

A red-black tree is a binary search tree where each node has a color (red/black).

Each time an insertion is performed, the newly inserted node is red, and the insertion process is the same as in a normal binary search tree.

If two red nodes become a parent-child pair, adjust as shown in the figure (the operations are left-right symmetric, and symmetric cases are not repeated in the figure; the black triangle represents null or a subtree rooted at a black node). The adjustment may need to be performed multiple times in a row.

After the adjustment, set the root to black.

Idea: ccz181078, Solution: ccz181078, Code: ccz181078, Data: ccz181078

Constraints: $1\leq n\leq 2\times 10^5$，$1\leq op\leq 2$，$1\leq x\leq 10^8$。

Translated by ChatGPT 5