P7910 [CSP-J 2021] Insertion Sort

Insertion sort is a very common and simple sorting algorithm. Little Z is a freshman in college, and today in class, Teacher H has just explained the insertion sort algorithm. Assume that comparing two elements takes $\mathcal O(1)$ time. Then insertion sort can sort an array of length $n$ in $\mathcal O(n^2)$ time. Suppose these $n$ numbers are stored in $a_1, a_2, \ldots, a_n$. The following pseudocode gives one of the simplest implementations of insertion sort: The following is sample code in C/C++: ```cpp for (int i = 1; i = 2; j--) if (a[j] < a[j-1]) { int t = a[j-1]; a[j-1] = a[j]; a[j] = t; } ``` The following is sample code in Pascal: ```pascal for i:=1 to n do for j:=i downto 2 do if a[j]

The first line contains two positive integers $n, Q$, representing the array length and the number of operations. The second line contains $n$ space-separated non-negative integers, where the $i$-th non-negative integer represents $a_i$. The next $Q$ lines each contain $2 \sim 3$ positive integers, representing one operation. The operation format is described in **Description**.

For each query of type $2$, output one line with one positive integer as the answer.

**Sample Explanation #1** Before the modification operation, suppose Teacher H performs one insertion sort. Then the positions of the three elements in the original sequence after sorting are $3, 2, 1$, respectively. After the modification operation, suppose Teacher H performs one insertion sort. Then the positions of the three elements in the original sequence after sorting are $3, 1, 2$, respectively. Note that although $a_2 = a_3$ at this time, we **cannot treat them as the same element**. **Sample #2** See the attached files `sort/sort2.in` and `sort/sort2.ans`. The Constraints for this test point are the same as test points $1 \sim 2$. **Sample #3** See the attached files `sort/sort3.in` and `sort/sort3.ans`. The Constraints for this test point are the same as test points $3 \sim 7$. **Sample #4** See the attached files `sort/sort4.in` and `sort/sort4.ans`. The Constraints for this test point are the same as test points $12 \sim 14$. **Constraints** For all testdata, $1 \le n \le 8000$, $1 \le Q \le 2 \times {10}^5$, $1 \le x \le n$, $1 \le v,a_i \le 10^9$. For all testdata, among all $Q$ operations, there are at most $5000$ operations of type $1$. The additional constraints and scores for each test point are shown in the table below. | Test Point | $n \le$ | $Q \le$ | Special Property | |:-:|:-:|:-:|:-:| | $1 \sim 4$ | $10$ | $10$ | None | | $5 \sim 9$ | $300$ | $300$ | None | | $10 \sim 13$ | $1500$ | $1500$ | None | | $14 \sim 16$ | $8000$ | $8000$| It is guaranteed that all input $a_i, v$ are pairwise distinct | | $17 \sim 19$ | $8000$ | $8000$ | None | | $20 \sim 22$ | $8000$ | $2 \times 10^5$ | It is guaranteed that all input $a_i, v$ are pairwise distinct | | $23 \sim 25$ | $8000$ | $2 \times 10^5$ | None | Translated by ChatGPT 5