P9673 [ICPC 2022 Jinan R] Quick Sort
题目描述
给定一个长度为 $n$ 的排列 $A$。现使用如下伪代码对 $A$ 进行排序：
```
procedure QUICKSORT(A,lo,hi)
if lo>=0 and hi>=0 and lo=pivot
repeat
j=j-1
until A[j]=j then
return j
end if
Swap A[i] with A[j]
end while
end procedure
```
试计算：调用 `QUICKSORT(A,1,n)` 函数过程中，`Swap` 操作执行了多少次。
输入格式
第一行包含一个整数 $T$ $(1\leqslant T\leqslant 10^5)$，表示测试数据组数。
对于每组测试数据：
第一行包含一个正整数 $n$ $(1\leqslant n\leqslant 5\times 10^5)$。
第二行包含 $n$ 个整数 $a_1,\dots,a_n$ $(1\leqslant a_i\leqslant n)$，表示排列 $A$。保证 $a_1,\dots,a_n$ 构成一个排列，即：$\forall i\not= j,a_i\not=a_j$。
保证所有测试数据中 $n$ 的和不超过 $5\times 10^5$。
输出格式
对于每组测试数据，输出一行一个整数，表示调用 `QUICKSORT(A,1,n)` 函数过程中，`Swap` 操作执行的次数。