{"problem":{"name":"[ICPC 2021 Nanjing R] Paimon Sorting","description":{"content":"Paimon just invents a new sorting algorithm which looks much like $\\textit{bubble sort}$, with a few differences. It accepts a $1$-indexed sequence $A$ of length $n$ and sorts it. Its pseudo-code is s","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9843"},"statements":[{"statement_type":"Markdown","content":"Paimon just invents a new sorting algorithm which looks much like $\\textit{bubble sort}$, with a few differences. It accepts a $1$-indexed sequence $A$ of length $n$ and sorts it. Its pseudo-code is shown below.\n\n```cpp\n// The Sorting Algorithm\nSORT(A)\n  for i from 1 to n // n is the number of elements if A\n    for j from 1 to n\n      if a[i] < a[j] // a[i] is the i-th element in A\n        Swap a[i] and a[j]\n```\n\nIf you don't believe this piece of algorithm can sort a sequence it will also be your task to prove it. Anyway here comes the question:\n\nGiven an integer sequence $A = a_1, a_2, \\cdots, a_n$ of length $n$, for each of its prefix $A_k$ of length $k$ (that is, for each $1 \\le k \\le n$, consider the subsequence $A_k = a_1, a_2, \\cdots, a_k$), count the number of swaps performed if we call $\\text{SORT}(A_k)$.\n\n## Input\n\nThere are multiple test cases. The first line of the input contains an integer $T$ indicating the number of test cases. For each test case:\n\nThe first line contains an integer $n$ ($1 \\le n \\le 10^5$) indicating the length of the sequence.\n\nThe second line contains $n$ integers $a_1, a_2, \\cdots, a_n$ ($1 \\le a_i \\le n$) indicating the given sequence.\n\nIt's guaranteed that the sum of $n$ of all test cases will not exceed $10^6$.\n\n## Output\n\nFor each test case output one line containing $n$ integers $s_1, s_2, \\cdots, s_n$ separated by a space, where $s_i$ is the number of swaps performed if we call $\\text{SORT}(A_i)$.\n\nPlease, DO NOT output extra spaces at the end of each line or your solution may be considered incorrect!\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9843","tags":["2021","Special Judge","O2优化","ICPC","南京"],"sample_group":[["3\n5\n2 3 2 1 5\n3\n1 2 3\n1\n1\n","0 2 3 5 7\n0 2 4\n0\n"]],"created_at":"2026-03-03 11:09:25"}}