F - 移动和逆序数

得分 : 600 分

问题描述

给定一个序列 $A = [a_0, a_1, a_2, \dots, a_{N-1}]$，其中 $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}$。

约束条件

• 输入中的所有值都是整数。
• $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$ 的情况的答案。

4
0 1 2 3

0
3
4
3

我们有 $A = [0, 1, 2, 3]$。

对于 $k = 0$，$B = [0, 1, 2, 3]$ 的逆序数为 $0$。
对于 $k = 1$，$B = [1, 2, 3, 0]$ 的逆序数为 $3$。
对于 $k = 2$，$B = [2, 3, 0, 1]$ 的逆序数为 $4$。
对于 $k = 3$，$B = [3, 0, 1, 2]$ 的逆序数为 $3$。

10
0 3 1 5 4 2 9 6 8 7

9
18
21
28
27
28
33
24
21
14