/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
0, 1, 2, \dots, N - 1 を並び替えた数列 A = [a_0, a_1, a_2, \dots, a_{N-1}] が与えられます。
k = 0, 1, 2, \dots, N - 1 のそれぞれについて、b_i = a_{i+k \bmod N} で定義される数列 B = [b_0, b_1, b_2, \dots, b_{N-1}] の転倒数を求めてください。
転倒数とは
数列 A = [a_0, a_1, a_2, \dots, a_{N-1}] の転倒数とは、i < j かつ a_i > a_j を満たす添字の組 (i, 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] の転倒数は 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 です。
入力例 2
10 0 3 1 5 4 2 9 6 8 7
出力例 2
9 18 21 28 27 28 33 24 21 14
Score : 600 points
Problem Statement
Given is a sequence A = [a_0, a_1, a_2, \dots, a_{N-1}] that is a permutation of 0, 1, 2, \dots, N - 1.
For each k = 0, 1, 2, \dots, N - 1, find the inversion number of the sequence B = [b_0, b_1, b_2, \dots, b_{N-1}] defined as b_i = a_{i+k \bmod N}.
What is inversion number?
The inversion number of a sequence A = [a_0, a_1, a_2, \dots, a_{N-1}] is the number of pairs of indices (i, j) such that i < j and a_i > a_j.Constraints
- All values in input are integers.
- 2 ≤ N ≤ 3 \times 10^5
- a_0, a_1, a_2, \dots, a_{N-1} is a permutation of 0, 1, 2, \dots, N - 1.
Input
Input is given from Standard Input in the following format:
N
a_0 a_1 a_2 \cdots a_{N-1}
Output
Print N lines.
The (i + 1)-th line should contain the answer for the case k = i.
Sample Input 1
4 0 1 2 3
Sample Output 1
0 3 4 3
We have A = [0, 1, 2, 3].
For k = 0, the inversion number of B = [0, 1, 2, 3] is 0.
For k = 1, the inversion number of B = [1, 2, 3, 0] is 3.
For k = 2, the inversion number of B = [2, 3, 0, 1] is 4.
For k = 3, the inversion number of B = [3, 0, 1, 2] is 3.
Sample Input 2
10 0 3 1 5 4 2 9 6 8 7
Sample Output 2
9 18 21 28 27 28 33 24 21 14