P9596 [JOI Open 2018] Bubble Sort 2 / Bubble Sort 2

Bubble sort is an algorithm for sorting a sequence. We want to sort a sequence $A_0, A_1, \ldots, A_{N-1}$ of length $N$ in non-decreasing order. When two adjacent numbers are not in the correct order, bubble sort swaps these two numbers. This kind of swapping is performed while scanning the sequence. More precisely, in one **scan**, for $i = 0, 1, \ldots, N - 2$ in this order, if $A_i > A_{i+1}$, then we swap these two numbers. It is well known that after a finite number of scans, any sequence can be sorted in non-decreasing order. For a sequence $A$, we define the **number of bubble sort scans** as the number of scans needed to sort $A$ using the algorithm above. JOI has a sequence $A$ of length $N$. He plans to process $Q$ queries that modify the values in $A$. More precisely, in the $(j+1)$-th query $(0 \le j \le Q - 1)$, the value of $A_{X_j}$ will be changed to $V_j$. JOI wants to know, after each modification, the number of bubble sort scans needed.

On LOJ this is an interactive problem. For convenience, here it is judged in the traditional (non-interactive) format. The first line contains two integers $N, Q$. The second line contains $N$ integers $A_0, A_1, \ldots, A_{N-1}$. The next $Q$ lines each contain two integers $X_j, V_j$.

Output $Q$ lines. The $(j+1)$-th line $(0 \le j \le Q - 1)$ should be the number of bubble sort scans for the sequence after processing the $(j+1)$-th query.

**Sample Explanation** Given a sequence of length $N = 4$, $A = \{1, 2, 3, 4\}$, and $Q = 2$ queries: $X = \{0, 2\}, V = \{3, 1\}$. 1. For the first query, the value of $A_0$ becomes $3$. We get $A = \{3, 2, 3, 4\}$. 2. For the second query, the value of $A_2$ becomes $1$. We get $A = \{3, 2, 1, 4\}$. Perform bubble sort on $A = \{3, 2, 3, 4\}$: - $A$ is not sorted, so the first scan starts. Since $A_0 > A_1$, we swap them, and the sequence becomes $A = \{2, 3, 3, 4\}$. Since $A_1 \le A_2$, we do not swap them. Since $A_2 \le A_3$, we also do not swap them. - Now $A$ is sorted, so the bubble sort process ends. Therefore, for $A = \{3, 2, 3, 4\}$, the number of bubble sort scans is $1$. Perform bubble sort on $A = \{3, 2, 1, 4\}$: - $A$ is not sorted, so the first scan starts. Since $A_0 > A_1$, we swap them, and the sequence becomes $A = \{2, 3, 1, 4\}$. Since $A_1 > A_2$, we swap them, and the sequence becomes $A = \{2, 1, 3, 4\}$. Since $A_2 \le A_3$, we also do not swap them. - $A$ is not sorted, so the second scan starts. Since $A_0 > A_1$, we swap them, and the sequence becomes $A = \{1, 2, 3, 4\}$. Since $A_1 \le A_2$, we do not swap them. Since $A_2 \le A_3$, we also do not swap them. - Now $A$ is sorted, so the bubble sort process ends. Therefore, for $A = \{3, 2, 1, 4\}$, the number of bubble sort scans is $2$. **Constraints** There are four subtasks. The score and additional constraints for each subtask are as follows: | Subtask ID | Score | $N$ | $Q$ | $A, V$ | | :--------: | :--: | :------------------: | :------------------: | :------------------------------: | | $1$ | $17$ | $1 \le N \le 2\ 000$ | $1 \le Q \le 2\ 000$ | $1 \le A_i, V_j \le 10^9$ | | $2$ | $21$ | $1 \le N \le 8\ 000$ | $1 \le Q \le 8\ 000$ | $1 \le A_i, V_j \le 10^9$ | | $3$ | $22$ | $1 \le N \le 50\ 000$ | $1 \le Q \le 50\ 000$ | $1 \le A_i, V_j \le 100$ | | $4$ | $40$ | $1 \le N \le 500\ 000$ | $1 \le Q \le 500\ 000$ | $1 \le A_i, V_j \le 10^9$ | Translated by ChatGPT 5