P6823 "EZEC-4" paulzrm Loves Array

Original statement: $\color{gray}\text{zrmpaul}$ has an array consisting of $n$ integers: $a_1,a_2,...,a_n$. The initial value of $a_i$ is $i(1\le i\le n)$. There are $m$ operations, including four types as follows. Type $1$: `1` sort the array. Type $2$: `2` sort the array and reverse it. Type $3$: `3 x y` swap $a_x,a_y$. **It is guaranteed that $x$ is not equal to $y$, and $1\leq x ,y \leq n$**. Type $4$: `4` reverse the array. You need to output the array after $m$ operations. First line with two intergers $n,m(1\leq n,m\leq 10^6)$. Next $m$ lines are the operations. One line, $n$ numbers, the array.

Xiao Z has a sequence of length $n$ with indices starting from $1$. Initially, the number at position $i$ is $i$. There are $m$ operations, and each operation is one of the following four types. - `1` Sort the sequence in increasing order. - `2` Sort the sequence in increasing order and then reverse it (i.e., sort in decreasing order). - `3 x y` Swap the numbers at indices $x$ and $y$. It is guaranteed that $x\ne y$ and $1\le x,y\le n$. - `4` Reverse the sequence. You need to output the sequence after $m$ operations.

The first line contains two integers $n,m$, representing the length of the sequence and the number of operations. The next $m$ lines each contain one operation. It is guaranteed that all operations are valid.

Output one line containing $n$ integers, representing the sequence after all operations.

Constraints **This problem uses bundled testdata.** subtask 1 (24 pts): $1\le n,m\le 2\times 10^3$. subtask 2 (13 pts): There is no operation of type 3. subtask 3 (63 pts): $1\le n,m\le 10^6$. Sample Explanation The operations applied to the sequence are: > $1, 2, 3, 4, 5$ $1, 2, 3, 4, 5$ $5, 4, 3, 2, 1$ $5, 2, 3, 4, 1$ $1, 4, 3, 2, 5$ $5, 4, 3, 2, 1$ Translated by ChatGPT 5