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