P7362 [eJOI 2020] XOR Sort (Day2)

Given a sequence $A_i$ of length $N$, you can perform the following operation: > Choose a position $i$ and change $A_i$ to $A_i \oplus A_{i+1}$ or $A_i \oplus A_{i-1}$. You want to know how many operations are needed to make $A_i$ become: - $S=1$, a strictly increasing sequence, i.e. $A_i < A_{i+1}$. - $S=2$, a non-strictly increasing sequence, i.e. $A_i \le A_{i+1}$.

The first line contains two integers $N, S$, representing the length of the sequence and the test point type. The second line contains $N$ integers $A_i$, representing the sequence.

The first line contains an integer $K$, representing the number of operations. You do not need to minimize $K$; you only need to satisfy $0 \le K \le 4 \times 10^4$. The next $K$ lines each contain two integers $i, j$, meaning to change $A_i$ to $A_i \oplus A_j$, where $j=i+1$ or $j=i-1$.

#### Explanation for Sample 1 $$[3, 2, 8, 4, 1] \to [\mathbf 1, 2, 8, 4, 1] \to [1, 2, 8, \mathbf{12}, 1] \to [1, 2, 8, 12, \mathbf{ 13}]$$ #### Explanation for Sample 2 $$[4, 4, 2, 0, 1] \to [4, 4, \mathbf6, 0, 1] \to [4, 4, 6, \mathbf6, 1] \to [4, 4, 6, 6, \mathbf7]$$ #### Constraints **This problem uses bundled testdata.** - Subtask 1 (25 pts): $2 \le N \le 150$, $S=1$, and all $A_i$ are distinct. - Subtask 2 (35 pts): $2 \le N \le 200$, $S=1$, and all $A_i$ are distinct. - Subtask 3 (40 pts): $2 \le N \le 1000$, $S=2$. For $100\%$ of the testdata: - $1 \le S \le 2$. - $2 \le N \le 1000$. - $0 \le A_i < 2^{20}$. **This problem uses Special Judge.** #### Note Translated from [eJOI 2020 Day2 A XOR Sort](https://ejoi2020.ge/static/assets/Day2/Problems/XorSort.pdf)。 Translated by ChatGPT 5