P10856 [MX-X2-T5] "Cfz Round 4" Xor-Forces

Original link: . --- ✿(。◕ᴗ◕。)✿

Given an array $a$ of length $n=2^k$ with indices starting from $0$, maintain $m$ operations: 1. Operation 1: Given $x$, define an array $a'$ such that $a'_i=a_{i\oplus x}$, and modify $a$ to $a'$. Here $\oplus$ denotes the bitwise XOR operation. 2. Operation 2: Given $l,r$, query how many color segments are in the subarray of $a$ whose indices are between $l$ and $r$. **It is not guaranteed that $\bm{l \le r}$. If $\bm{l > r}$, please swap $\bm{l,r}$ yourself.** Here, a color segment is defined as a maximal subarray in which all numbers are equal. Some test points require strict online processing.

The first line contains three integers $T,k,m$, where $T \in \{ 0, 1 \}$ is a parameter that decides whether strict online processing is required. The second line contains $n$ integers $a_0, \ldots, a_{n-1}$. Then follow $m$ lines. Each line contains two or three integers describing one operation. The first integer $\mathit{op}$ indicates the operation type. - If $op=1$, it is Operation 1. The next integer is $x'$, satisfying $x=x'\oplus(T\times \mathit{lst})$. - If $op=2$, it is Operation 2. The next two integers are $l',r'$, satisfying $l=l'\oplus(T\times \mathit{lst})$, $r=r'\oplus(T\times \mathit{lst})$. **It is not guaranteed that $\bm{l \le r}$. If $\bm{l > r}$, please swap $\bm{l, r}$ yourself.** - Here $\mathit{lst}$ denotes the answer to the previous query. In particular, if there has been no query before, then $\mathit{lst}=0$.

Output several lines. Each line contains one integer, in order, representing the answer to each query.

**[Sample Explanation #1]** This sample allows offline processing. Initially, $a=[1,2,1,3,2,4,5,1]$. The subarray of $a$ with indices between $1$ and $5$ is $[2,1,3,2,4]$, and its number of color segments is $5$. After the rearrangement operation, $a=[3,1,2,1,1,5,4,2]$. The subarray of $a$ with indices between $5$ and $1$ is $[1,2,1,1,5]$, and its number of color segments is $4$. **[Sample Explanation #2]** Except for strict online processing, this sample is exactly the same as Sample \#1. **[Constraints]** For all testdata, $T \in \{ 0, 1 \}$, $0\le k\le 18$, $n=2^k$, $1\le m\le 2\times 10^5$, $1\le a_i\le n$, $\mathit{op} \in \{ 1, 2 \}$, $0\le x,l,r < n$. **This problem uses bundled testcases.** - Subtask 1 (15 points): $T=1$, $k\le 10$, $m\le 10^3$. - Subtask 2 (15 points): $T=1$, there is no Operation 1. - Subtask 3 (20 points): $T=1$, for all Operation 2 queries, either $l=0,r=n-1$, or $l=n-1,r=0$. - Subtask 4 (20 points): $T=0$. - Subtask 5 (30 points): $T=1$. **Note: Subtask 5 depends on the first four subtasks. Only after passing the first four subtasks can you try to obtain the score for this subtask.** Translated by ChatGPT 5