atcoder#ABC190F. [ABC190F] Shift and Inversions

[ABC190F] Shift and Inversions

题目描述

0, 1, 2, , N  1 0,\ 1,\ 2,\ \dots,\ N\ -\ 1 を並び替えた数列 A = [a0, a1, a2, , aN1] A\ =\ [a_0,\ a_1,\ a_2,\ \dots,\ a_{N-1}] が与えられます。
k = 0, 1, 2, , N  1 k\ =\ 0,\ 1,\ 2,\ \dots,\ N\ -\ 1 のそれぞれについて、bi = ai+k mod N b_i\ =\ a_{i+k\ \bmod\ N} で定義される数列 B = [b0, b1, b2, , bN1] B\ =\ [b_0,\ b_1,\ b_2,\ \dots,\ b_{N-1}] の転倒数を求めてください。

転倒数とは 数列 A = [a0, a1, a2, , aN1] A\ =\ [a_0,\ a_1,\ a_2,\ \dots,\ a_{N-1}] の転倒数とは、i かつ ai > aj i\ かつ\ a_i\ >\ a_j を満たす添字の組 (i, j) (i,\ j) の個数のことです。

输入格式

入力は以下の形式で標準入力から与えられる。

N N a0 a_0 a1 a_1 a2 a_2 \cdots aN1 a_{N-1}

输出格式

N N 行出力せよ。
i + 1 i\ +\ 1 行目には、k = i k\ =\ i としたときの答えを出力せよ。

题目大意

nn00nn - 11 全排列的数组,然后这个数组会循环左移 nn - 11, 求这个过程中数组的逆序数对是多少?

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 × 105 2\ <\ =\ N\ <\ =\ 3\ \times\ 10^5
  • a0, a1, a2, , aN1 a_0,\ a_1,\ a_2,\ \dots,\ a_{N-1} 0, 1, 2, , N  1 0,\ 1,\ 2,\ \dots,\ N\ -\ 1 の並び替えである

Sample Explanation 1

A = [0, 1, 2, 3] A\ =\ [0,\ 1,\ 2,\ 3] です。 k = 0 k\ =\ 0 のとき、B = [0, 1, 2, 3] B\ =\ [0,\ 1,\ 2,\ 3] の転倒数は 0 0 です。 k = 1 k\ =\ 1 のとき、B = [1, 2, 3, 0] B\ =\ [1,\ 2,\ 3,\ 0] の転倒数は 3 3 です。 k = 2 k\ =\ 2 のとき、B = [2, 3, 0, 1] B\ =\ [2,\ 3,\ 0,\ 1] の転倒数は 4 4 です。 k = 3 k\ =\ 3 のとき、B = [3, 0, 1, 2] B\ =\ [3,\ 0,\ 1,\ 2] の転倒数は 3 3 です。