P10009 [CTT Mutual Test 2022] Segment Tree

Please note: **this problem is not a segment tree template problem**.

You are given a sequence $a_1,a_2,\cdots a_n$ of length $n$. You need to perform a total of $q$ operations of the following two types: - `1 l r`: Replace $a_{l\sim r}$ with its XOR difference. Formally, let $b_i := a_i \text{ xor } a_{i-1}$ ($l

The first line contains an integer $T$, indicating that the input satisfies the constraints of the $T$-th subtask. The second line contains two integers $n,q$, representing the length of the sequence and the number of operations. The third line contains $n$ integers $a_1,a_2,\cdots,a_n$. In the next $q$ lines, each line contains several numbers describing one operation. If it is the first type of operation, the line contains three numbers `1 l r`. If it is the second type of operation, the line contains two numbers `2 pos`.

Suppose there are $q_2$ operations of the second type. Output a total of $q_2+n$ lines. In the first $q_2$ lines, output one integer per line, which is the answer to that query. In the next $n$ lines, output one integer per line, which is the final sequence $a$.

**More samples can be found in the attached file**. For the $(i + 1)$-th sample, $T = i$. ### Sample 1 Explanation Initially, $a=[1,1,5,1,9,4]$. The first operation asks to output $a_5$. At this time, $a_5=9$, so output $9$. The second operation asks to replace $a_{2\sim 5}$ with its XOR difference. $a_{2\sim 5}$ is $[1,5,1,9]$, and its XOR difference is $[1,4,4,8]$. Therefore, after this operation, the sequence $a$ becomes $[1,1,4,4,8,4]$. The third operation asks to output $a_4$. At this time, $a_4=4$, so output $4$. The fourth operation asks to replace $a_{3\sim 6}$ with its XOR difference. $a_{3\sim 6}$ is $[4,4,8,4]$, and its XOR difference is $[4,0,12,12]$. Therefore, after this operation, the sequence $a$ becomes $[1,1,4,0,12,12]$. The fifth operation asks to output $a_6$. At this time, $a_6=12$, so output $12$. The sixth operation asks to replace $a_{1\sim 6}$ with its XOR difference. $a_{1\sim 6}$ is $[1,1,4,0,12,12]$, and its XOR difference is $[1,0,5,4,12,0]$. Therefore, after this operation, the sequence $a$ becomes $[1,0,5,4,12,0]$. The final sequence $a$ is $[1,0,5,4,12,0]$. ### Constraints and Notes For all testdata, it is guaranteed that $1\leq n\leq 2.5\times 10^5$, $1\leq q\leq 10^5$, $0\leq a_i< 2^{30}$, $1\leq l\leq r\leq n$, and $1\leq pos\leq n$. | Subtask ID | $n\leq$ | $q\leq$ | Special Property | Score | Subtask Dependencies | | :--------: | :--------------: | :------------: | :--------------: | :---: | :----------------------: | | $1$ | $2\times 10^3$ | $2\times 10^3$ | None | $8$ | None | | $2$ | $2.5\times 10^5$ | $10^5$ | A | $4$ | None | | $3$ | $2.5\times 10^5$ | $10^5$ | B | $7$ | None | | $4$ | $2.5\times 10^5$ | $10^5$ | CD | $13$ | None | | $5$ | $2.5\times 10^5$ | $10^5$ | DE | $12$ | None | | $6$ | $2.5\times 10^5$ | $10^5$ | D | $16$ | $5$ | | $7$ | $2.5\times 10^5$ | $10^5$ | E | $11$ | $5$ | | $8$ | $2.5\times 10^5$ | $10^5$ | None | $29$ | $1,2,3,4,5,6,7$ | Special Property A: $\forall i\geq 2, a_i=0$. Special Property B: $0\leq a_i\leq 1$. Special Property C: Let $c$ be the number of non-zero positions in the sequence $a$. Then $c\leq 100$. Special Property D: For operation $1$, it holds that $l=1$ and $r=n$. Special Property E: There is no operation $2$. Translated by ChatGPT 5