ページが読み込まれませんか？ こちらをクリックすると直るかもしれません。
Placeholder

#4168

Haircut 1s 512MB

問題

Tired of his stubborn cowlick, Farmer John decides to get a haircut. He has N (1\le N\le 10^5) strands of hair arranged in a line, and strand i is initially A_i micrometers long (0\le A_i\le N). Ideally, he wants his hair to be monotonically increasing in length, so he defines the "badness" of his hair as the number of inversions: pairs (i,j) such that i < j and A_i > A_j.

For each of j=0,1,\ldots,N-1, FJ would like to know the badness of his hair if all strands with length greater than j are decreased to length exactly j.

(Fun fact: the average human head does indeed have about 10^5 hairs!)

SCORING:

  • Test case 2 satisfies N\le 100.

  • Test cases 3-5 satisfy N\le 5000.

  • Test cases 6-13 satisfy no additional constraints.

Problem credits: Dhruv Rohatgi


入力

The first line contains N.

The second line contains A_1,A_2,\ldots,A_N.


出力

For each of j=0,1,\ldots,N-1, output the badness of FJ's hair on a new line.

Note that the large size of integers involved in this problem may require the use of 64-bit integer data types (e.g., a "long long" in C/C++).


例題 

5
5 2 3 3 0
0
4
4
5
7

The fourth line of output describes the number of inversions when FJ's hairs are decreased to length 3. Then A=[3,2,3,3,0] has five inversions: A_1>A_2,\,A_1>A_5,\,A_2>A_5,\,A_3>A_5, and A_4>A_5.



出典

USACO 2020 US Open Gold

ログインしないとコードを書けません。