1301: Bubbling bubbles
题目
题目描述
给定一个长度为 $n$ 的排列，元素标号为 $1 \dots n$。
如果对这个排列进行冒泡排序，那么每个元素会被交换若干次。
请输出每个元素在进行冒泡排序时，参与了多少次交换。
我们将以以下代码为标准计算交换次数。
cpp
void bubble_sort(int a[], int n) {
for (int i = 1; i < n; i++) {
for (int j = 0; j < n - i; j++) {
if (a[j] > a[j + 1]) {
swap(a[j], a[j + 1]);
}
} // after i-th inner iteration, a[n - i] is correct
}
}
Input
请从 stdin 读入。
输入第一行一个正整数 $n (1 \leq n \leq 10^6)$ 。
第二行包含 $n$ 个空格隔开整数表示排列，第 $i$ 个数为排列第 $i$ 位 $a_i (1 \leq a_i \leq n)$。输入保证 $n$ 个数互不相同。
Output
请输出到 stdout 中。
输出一行 $n$ 个由空格隔开的数，第 $i$ 个数表示 $i$ 被交换了多少次。
Sample Input
txt
4
1 2 3 4
txt
4
4 3 2 1
txt
3
2 3 1
Sample Output
txt
0 0 0 0
txt
3 3 3 3
txt
2 1 1
Constraints
Time Limit: 1s
Memory Limit: 512MB
Oops! 本题目还没有解答！
助教老师们编题的速度，已经超过了解题的速度！
OJ翻了一新，但本解答集还大多用的是2017-2019级，甚至更早的同学们贡献的答案。
如果你已经AC了，可以的话，请您参考添加页面，与大家一起分享你的题解！