分数: 600 点
问题陈述
给定的是一个序列 A = [a_0, a_1, a_2, \dots, a_{N-1}] 这是一个排列 0, 1, 2, \dots, N - 1.
对于每个 k = 0, 1, 2, \dots, N - 1,求序列的倒数 B = [b_0, b_1, b_2, \dots, b_{N-1}] 定义为 b_i = a_{i+k \bmod N}.
什么是反转数?
序列的反转数 A = [a_0, a_1, a_2, \dots, a_{N-1}] 是索引对的数量 (i, j) 这样 i < j 和 a_i > a_j.约束
- 输入中的所有值都是整数。
- 2 ≤ N ≤ 3 \times 10^5
- a_0, a_1, a_2, \dots, a_{N-1} 是一个排列 0, 1, 2, \dots, N - 1.
输入
输入由标准输入按以下格式给出:
N
a_0 a_1 a_2 \cdots a_{N-1}
输出
打印 N 行。
的 (i + 1)- 第行应包含案例的答案 k = i.
示例输入 1
4 0 1 2 3
示例输出 1
0 3 4 3
我们有 A = [0, 1, 2, 3].
对于 k = 0,反转数 B = [0, 1, 2, 3] is 0.
对于 k = 1,反转数 B = [1, 2, 3, 0] is 3.
对于 k = 2,反转数 B = [2, 3, 0, 1] is 4.
对于 k = 3,反转数 B = [3, 0, 1, 2] is 3.
示例输入 2
10 0 3 1 5 4 2 9 6 8 7
示例输出 2
9 18 21 28 27 28 33 24 21 14