Background

Original link: https://oier.team/problems/X2E.

✿(。◕ᴗ◕。)✿

Problem Description

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.

Input Format

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 Format

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

0 3 3
1 2 1 3 2 4 5 1
2 1 5
1 3
2 5 1

5
4

1 3 3
1 2 1 3 2 4 5 1
2 1 5
1 6
2 0 4

5
4

1 4 16
12 9 5 9 12 12 9 12 9 16 5 9 12 16 9 5
2 0 4
1 15
2 14 0
1 15
2 6 0
2 4 14
1 0
1 14
2 4 10
2 6 3
1 7
2 4 13
1 3
1 3
2 4 3
2 15 2

5
7
4
7
9
5
7
2
11

Hint

[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