P5055 [Template] Persistent “Literary” Balanced Tree

This is a template problem.

You need to implement a data structure to maintain a sequence, supporting the following operations (**for every past historical version**): 1. Insert a number $x$ after the $p$-th number. 2. Delete the $p$-th number. 3. Reverse the interval $[l,r]$. For example, if the original sequence is $\{5,4,3,2,1\}$, after reversing $[2,4]$, it becomes $\{5,2,3,4,1\}$. 4. Query the sum of all numbers in the interval $[l,r]$. **Different from an ordinary balanced tree, every operation is performed based on some historical version, and generates a new version (operation $4$ keeps the original version unchanged). The new version is numbered as the index of this operation.** **This problem is strictly online.**

The first line contains an integer $n$, the total number of operations. The next $n$ lines each start with two integers $v_i, \mathrm{opt}_i$. Here, $v_i$ is the index of the past version it is based on ($0 \le v_i < i$), and $\mathrm{opt}_i$ is the operation type ($1 \le \mathrm{opt}_i \le 4$). If $\mathrm{opt}_i=1$, then two more integers $p_i, x_i$ follow, meaning: insert number $x$ after the $p_i$-th number. If $\mathrm{opt}_i=2$, then one more integer $p_i$ follows, meaning: delete the $p_i$-th number. If $\mathrm{opt}_i=3$, then two more integers $l_i, r_i$ follow, meaning: reverse the interval $[l_i, r_i]$. If $\mathrm{opt}_i=4$, then two more integers $l_i, r_i$ follow, meaning: query the sum of the interval $[l_i, r_i]$. **Strict online rule:** **Let the answer of the last operation of type $4$ before the current operation be $lastans$ (if there is no previous type $4$ operation, then $lastans=0$).** **Then $p_i,x_i$ or $l_i,r_i$ of this operation are each XORed bitwise with $lastans$ to obtain the real $p_i,x_i$ or $l_i,r_i$.**

For each query operation with type $4$, output one line with one number: the sum of the interval.

:::info[Sample Explanation] The sample input: ``` 10 0 1 0 1 1 1 1 2 2 4 1 2 3 1 1 3 4 4 1 2 5 3 1 3 6 4 1 2 4 1 2 4 8 3 1 3 9 4 1 4 ``` After all operations, a total of $11$ versions are generated: Version $0$ (initial version): $\varnothing$ Version $1$: $\{1\}$ Version $2$: $\{1,2\}$ Version $3$: $\{1,2\}$ (this operation queries the sum on $\left[1,2\right]$ and outputs $3$.) Version $4$: $\{1,3,2\}$ Version $5$: $\{1,3,2\}$ (this operation queries the sum on $\left[1,2\right]$ and outputs $4$.) Version $6$: $\{2,3,1\}$ Version $7$: $\{2,3,1\}$ (this operation queries the sum on $\left[1,2\right]$ and outputs $5$.) Version $8$: $\{1,3,4,2\}$ Version $9$: $\{4,3,1,2\}$ Version $10$: $\{4,3,1,2\}$ (this operation queries the sum on $\left[1,4\right]$ and outputs $10$.) :::: **Strict online: the following constraints on $p_i, x_i, l_i, r_i$ are after XORing with $lastans$.** - For $6$ test points, $n \le 5000$. - For another $6$ test points, $v_i = i - 1$. - Users are welcome to strengthen the testdata. You may contact the administrator or the problem setter. For $100\%$ of the data, $1 \le n \le 2 \times {10}^5$, $|x_i| < {10}^6$. Assume the sequence length of the referenced historical version is $len \ge 1$, then: If $\mathrm{opt}_i=1$, then $0 \le p_i \le len$. If $\mathrm{opt}_i=2$, then $1 \le p_i \le len$. If $\mathrm{opt}_i=3$, then $1 \le l_i \le r_i \le len$. If $\mathrm{opt}_i=4$, then $1 \le l_i \le r_i \le len$. Assume the sequence length of the referenced historical version is $0$, then: $\mathrm{opt}_i=1$, $p_i=0$. Translated by ChatGPT 5