P6136 [Template] Ordinary Balanced Tree (Enhanced testdata version)

This problem is the enhanced testdata version of P3369. It **expands the constraints** and adds **forced online**. **The input and output of this problem are slightly different from the original one**, but the operations that need to be supported are the same.

You need to dynamically maintain a multiset $M$, and provide the following operations: 1. Insert a number $x$ into $M$. 2. Delete a number $x$ from $M$ (if there are multiple identical numbers, delete only one). 3. Query how many numbers in $M$ are less than $x$, and then add $1$ to the result. 4. Query the number whose rank is the $x$-th when $M$ is sorted in increasing order. 5. Query the predecessor of $x$ in $M$ (the predecessor is defined as the largest number less than $x$). 6. Query the successor of $x$ in $M$ (the successor is defined as the smallest number greater than $x$). This problem is **forced online**. All operations are guaranteed to be valid (for operation $2$, there is guaranteed to be at least one $x$; for operations $4,5,6$, an answer is guaranteed to exist).

The first line contains two positive integers $n,m$, representing the **number of initial numbers** and the number of operations. **The second line contains $n$ integers $a_1,a_2,a_3,\ldots,a_n$, representing the initial numbers**. Next there are $m$ lines, each containing two integers $\text{opt}$ and $x'$. $\text{opt}$ indicates the operation index ($ 1 \leq \text{opt} \leq 6 $), and $x'$ indicates the encrypted operand. Let $\text{last}$ denote the answer of the most recent operation among $3,4,5,6$. Then in each operation, the real $x$ is obtained by XORing $x'$ with $\text{last}$. Initially, $\text{last}=0$.

Output one line with one integer, representing the **XOR sum** of the answers of all operations $3,4,5,6$.

### Sample Explanation Before encryption, the sample is: ```plain 6 7 1 1 4 5 1 4 2 1 1 9 4 1 5 9 3 8 6 1 1 0 ``` ::::info[Output of each operation] Before the first operation, $M=\{1,1,1,4,4,5\}$. After it, $M=\{1,1,4,4,5\}$. After the second operation, $M=\{1,1,4,4,5,9\}$. The third operation queries the $1$-st smallest number in $M$, and the answer is $1$. The fourth operation queries the predecessor of $9$ in $M$, and the answer is $5$. The fifth operation queries how many numbers in $M$ are less than $8$, and then adds $1$ to the result. The answer is $6$. The sixth operation queries the successor of $1$ in $M$, and the answer is $4$. After the seventh operation, $M=\{0,1,1,4,4,5,9\}$. The output is $1\oplus5\oplus6\oplus4=6$. :::: ### Limits and Notes For $100\%$ of the testdata, $1\leq n\leq 10^5$, $1\leq m\leq 10^6$, $0\leq a_i,x\lt 2^{30}$. **The input size of this problem is large. Please use a fast input method.** --- $\text{upd 2022.7.22}$: Added $9$ new sets of hack testdata. Translated by ChatGPT 5