P1975 [CTT] Queueing

Enhanced version: .

Sit in a row and eat fruit; the fruit is sweet and tasty, everyone smiles happily. One for you, one for me; the big one goes to you, the small one stays with me. After we finish eating, we sing a song, and everyone is cheerful. The children of Red Star Kindergarten line up in a long queue to eat fruit. However, because their heights differ, the queue looks uneven and not very neat. Let the height of the $i$-th child be $h_i$. Each time, the teacher selects two children and swaps their positions. Please help compute the number of inversions in the sequence after each swap. For the teacher’s convenience, you should also output the inversion count of the sequence before any swaps are performed. # Description

- The first line contains a positive integer $n$, the number of children. - The second line contains $n$ space-separated positive integers $h_1, h_2, \dots, h_n$, representing the heights in the initial queue. - The third line contains a positive integer $m$, the number of swap operations. - The following $m$ lines each contain two positive integers $a_i, b_i$, indicating that the children at positions $a_i$ and $b_i$ are swapped.

Output $m+1$ lines. - Line 1: the number of inversions in the sequence before any swap. - For $i = 1, 2, \dots, m$, line $i+1$: the number of inversions in the sequence after performing swap $i$.

[Sample explanation] Before any operation, $(2,3)$ is an inversion. After operation 1, the sequence is $130 \ 140 \ 150$, and there are no inversions. After operation 2, the sequence is $150 \ 140 \ 130$, and $(1,2)$, $(1,3)$, $(2,3)$ are inversions, totaling $3$. [Constraints] For $10\%$ of the testdata, $n, m \le 15$. For $25\%$ of the testdata, $n, m \le 200$. Additionally, for $25\%$ of the testdata, all $h_i$ are distinct. Additionally, for $15\%$ of the testdata, $110 \le h_i \le 160$. These two types of testdata are disjoint. For $100\%$ of the testdata, $1 \le m \le 2 \times 10^3$, $1 \le n \le 2 \times 10^4$, $1 \le h_i \le 10^9$, $a_i \ne b_i$, and $1 \le a_i, b_i \le n$. Translated by ChatGPT 5