P8449 [LSOT-1] Inversion Pairs

Inversion pairs are really fun.

You need to maintain a sequence and support the following $4$ operations: 1. Swap two intervals. 2. Move an interval **backward** to between the $k$-th number and the $(k+1)$-th number. 3. Insert a number $x$ at the end. 4. Insert a number $x$ at the beginning. After each operation, the indices of the numbers are re-numbered in the new sequence from the first number to the $k$-th number as $1$ to $k$. Now, after every operation, please output the parity of the number of inversion pairs in the entire sequence.

The first line contains two positive integers $n,m$, representing the length of the initial sequence and the number of operations. The next line contains $n$ positive integers $a_1,a_2,\dots,a_n$, representing the initial sequence. The next $m$ lines each start with an integer $t$ indicating the operation type, followed by: - If $t=1$, input four positive integers $l_1,r_1,l_2,r_2$, meaning to swap the whole interval $[l_1,r_1]$ with the whole interval $[l_2,r_2]$. It is guaranteed that $l_1\le r_1< l_2\le r_2$. - If $t=2$, input three positive integers $l,r,k$, meaning to move the interval $[l,r]$ to between the $k$-th number and the $(k+1)$-th number of the sequence. It is guaranteed that $r

After each operation, if the number of inversion pairs is even, output `even`; otherwise output `odd`.

[Sample Explanation] In the first operation, swap interval $[1,1]$ and interval $[2,2]$. The sequence becomes `3 4 5 7 2 6`. In the second operation, move interval $[1,1]$ to between the $3$-rd and the $4$-th numbers. The sequence becomes `4 5 3 7 2 6`. In the third operation, insert $11$ at the end of the sequence. The sequence becomes `4 5 3 7 2 6 11`. In the fourth operation, insert $1$ at the beginning of the sequence. The sequence becomes `1 4 5 3 7 2 6 11`. [Constraints] **"This problem uses bundled testdata."** - $\texttt{Subtask 1(10 pts): }n,m\le 10^2$. - $\texttt{Subtask 2(15 pts): }n,m\le 10^3$. - $\texttt{Subtask 3(20 pts): }$Operations 1 and 2 do not appear. - $\texttt{Subtask 4(20 pts): }$Operations 3 and 4 do not appear. - $\texttt{Subtask 5(35 pts): }$No special restrictions. For $100\%$ of the testdata, $1\le n,m \le 2\times 10^5$, $a_i\le 2\times10^6$, and it is guaranteed that all numbers in $a$ are distinct at any time. Translated by ChatGPT 5