P6186 [NOI Online #1 Senior] Bubble Sort

You are given a permutation $p_i$ of $1 \sim n$. Then there are $m$ operations, of two types: 1. Swap operation: given $x$, swap the $x$-th number and the $(x+1)$-th number in the current permutation. 2. Query operation: given $k$, find the number of inversions in the current permutation after performing $k$ rounds of bubble sort. The pseudocode for performing one round of bubble sort on a permutation $p_i$ of length $n$ is: ``` for i = 1 to n-1: if p[i] > p[i + 1]: swap(p[i], p[i + 1]) ```

The first line contains two integers $n$ and $m$, representing the length of the permutation and the number of operations. The second line contains $n$ integers representing the permutation $p_i$. The next $m$ lines each contain two integers $t_i$ and $c_i$, describing an operation: - If $t_i = 1$, then this operation is a swap operation, and $x = c_i$. - If $t_i = 2$, then this operation is a query operation, and $k = c_i$.

For each query operation, output one line with one integer representing the answer.

#### Explanation for Sample 1 First operation: the permutation is $\{1,2,3\}$. After $0$ rounds of bubble sort it is $\{1,2,3\}$, with $0$ inversions. Second operation: the permutation becomes $\{2,1,3\}$. Third operation: the permutation becomes $\{2,3,1\}$. Fourth operation: after $0$ rounds of bubble sort the permutation is $\{2,3,1\}$, with $2$ inversions. Fifth operation: after $1$ round of bubble sort the permutation becomes $\{2,1,3\}$, with $1$ inversion. Sixth operation: after $2$ rounds of bubble sort the permutation becomes $\{1,2,3\}$, with $0$ inversions. --- #### Constraints and Notes For testdata 1 $\sim$ 2: $n, m \leq 100$. For testdata 3 $\sim$ 4: $n, m \leq 2000$. For testdata 5 $\sim$ 6: the number of swap operations does not exceed $100$. For all testdata: $2 \leq n, m \leq 2 \times 10^5$, $t_i \in \{1,2\}$, $1 \leq x < n$, $0 \leq k < 2^{31}$. Translated by ChatGPT 5