#PU1041. USACO 2020 US Open Contest, Gold — Problem 1. Haircut
USACO 2020 US Open Contest, Gold — Problem 1. Haircut
USACO 2020 US Open Contest, Gold — Problem 1. Haircut
题目描述
Tired of his stubborn cowlick, Farmer John decides to get a haircut. He has () strands of hair arranged in a line, and strand is initially micrometers long (). 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 such that and . For each of , FJ would like to know the badness of his hair if all strands with length greater than are decreased to length exactly . (Fun fact: the average human head does indeed have about hairs!)
输入格式
The first line contains . The second line contains
输出格式
For each of , output the badness of FJ's hair on a new line.
数据范围
Test case 2 satisfies Test cases 3-5 satisfy Test cases 6-13 satisfy no additional constraints. Problem credits: Dhruv Rohatgi
样例
样例 1
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$.
提示
use of 64-bit integer data types (e.g., a "long long" in C/C++).