Shift and Inversions

题目描述

给定一个序列 $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}$。

输入格式

输入以标准输入给出，格式如下： $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

10
0 3 1 5 4 2 9 6 8 7

9
18
21
28
27
28
33
24
21
14

提示

输入中的所有值均为整数。 $2 ≤ N ≤ 3 \times 10^5$ $a_0, a_1, a_2, \dots, a_{N-1}$ 是 $0, 1, 2, \dots, N - 1$ 的一个排列。我们有 $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$。

标签: AtCoder|abc190F

来源

AtCoder|abc190F