P3835 [Template] Persistent Balanced Tree

This problem is a persistent enhanced version of the problem Ordinary Balanced Tree. The testdata has been strengthened. Thanks to @Kelin for providing a set of hack testdata.

You need to implement a data structure (refer to the problem title) to maintain a multiset of integers, and support the following operations for each historical version: 1. Insert $x$. 2. Delete $x$ (if there are multiple equal numbers, delete only one; if none exists, ignore this operation). 3. Query the rank of $x$ (rank is defined as the number of elements strictly less than $x$, plus $1$). 4. Query the number whose rank is $x$. 5. Query the predecessor of $x$ (the predecessor is defined as the largest number strictly less than $x$; if it does not exist, output $-2^{31}+1$). 6. Query the successor of $x$ (the successor is defined as the smallest number strictly greater than $x$; if it does not exist, output $2^{31}-1$). Unlike the original balanced tree, every operation here is based on some historical version and produces a new version. (Operations 3, 4, 5, 6 do not modify the original version.) Each version is numbered by the operation index (version $0$ is the initial state, an empty tree).

The first line contains a positive integer $n$, the total number of operations. The next $n$ lines each contain three integers. On the $i$-th line, they are $v_i, \text{opt}_i, x_i$. $v_i$ is the index of the past version to base on, $\text{opt}_i$ is the operation type, and $x_i$ is the value involved in the operation.

Each line contains one integer, in order, corresponding to the answers for operations $3, 4, 5, 6$.

Constraints For $28\%$ of the testdata, $1 \leq n \leq 10$. For $44\%$ of the testdata, $1 \leq n \leq 2 \times 10^2$. For $60\%$ of the testdata, $1 \leq n \leq 3 \times 10^3$. For $84\%$ of the testdata, $1 \leq n \leq 10^5$. For $92\%$ of the testdata, $1 \leq n \leq 2 \times 10^5$. For $100\%$ of the testdata, $1 \leq n \leq 5 \times 10^5$, $|x_i| \leq 10^9$, $0 \le v_i < i$, $1 \le \text{opt} \le 6$. Empirically, persistent balanced trees with normal constant factors can pass. Please rest assured. Sample explanation: There are $10$ operations and $11$ versions. The states of each version are: 0. $[]$ 1. $[9]$ 2. $[3, 9]$ 3. $[9, 10]$ 4. $[3, 9]$ 5. $[9, 10]$ 6. $[2, 9, 10]$ 7. $[2, 9, 10]$ 8. $[2, 10]$ 9. $[2, 10]$ 10. $[3, 9]$ Translated by ChatGPT 5