{"problem":{"name":"[ICPC 2022 Jinan R] Quick Sort","description":{"content":"When Prof. Pang was young, he wrote the following code for quick sort. Please calculate how many swaps are performed when calling $\\text{quicksort}(A, 1, n)$. $A$ is a given permutation with length $n","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":5000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9673"},"statements":[{"statement_type":"Markdown","content":"When Prof. Pang was young, he wrote the following code for quick sort. Please calculate how many swaps are performed when calling $\\text{quicksort}(A, 1, n)$. $A$ is a given permutation with length $n$.\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/8ig9i3bq.png)\n\n## Input\n\nThe first line contains one integer $T~(1\\le T \\le 10^5)$, the number of test cases.\n\nFor each test case, the first line contains one positive integer $n~(1\\le n \\le 5\\times 10^5)$. The next line contains $n$ integers $a_1,\\ldots, a_n~(1 \\le a_i\\le n)$ denoting the permutation $A$. It is guaranteed that $a_1,\\ldots, a_n$ form a permutation, i.e.~$a_i\\neq a_j$ for $i \\neq j$. \n\nIt is guaranteed that the sum of $n$ over all test cases is no more than $5\\times 10^5$.\n\n## Output\n\nFor each test case, output one line containing the number of swaps performed when calling $\\text{quicksort}(A, 1, n)$.\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9673","tags":["2022","O2优化","ICPC","济南"],"sample_group":[["3\n3\n3 2 1\n5\n2 4 5 3 1\n10\n7 2 4 6 1 9 10 8 5 3","1\n4\n7"]],"created_at":"2026-03-03 11:09:25"}}