AT_abc190_f [ABC190F] Shift and Inversions

题目描述

给定一个由 $0, 1, 2, \dots, N-1$ 组成的排列数列 $A = [a_0, a_1, a_2, \dots, a_{N-1}]$。

对于 $k = 0, 1, 2, \dots, N-1$ 的每一个 $k$，定义数列 $B = [b_0, b_1, b_2, \dots, b_{N-1}]$，其中 $b_i = a_{(i + k) \bmod N}$。

请你求出每个 $B$ 的逆序对数。

逆序对数指的是，对于数列 $A = [a_0, a_1, a_2, \dots, a_{N-1}]$，满足 $i < j$ 且 $a_i > a_j$ 的下标对 $(i, j)$ 的个数。

输入格式

输入通过标准输入给出，格式如下：

$N$ $a_0$ $a_1$ $a_2$ $\cdots$ $a_{N-1}$

输出格式

输出共 $N$ 行。
第 $i+1$ 行输出当 $k = i$ 时的答案。

输入输出样例 #1

输入 #1

4
0 1 2 3

输出 #1

0
3
4
3

输入输出样例 #2

输入 #2

10
0 3 1 5 4 2 9 6 8 7

输出 #2

9
18
21
28
27
28
33
24
21
14

说明/提示

限制条件

• 输入均为整数。
• $2 \leq N \leq 3 \times 10^5$
• $a_0, a_1, a_2, \dots, a_{N-1}$ 是 $0, 1, 2, \dots, N-1$ 的一个排列。

样例解释 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$。

由 ChatGPT 4.1 翻译