#PU1041. USACO 2020 US Open Contest, Gold — Problem 1. Haircut

    ID: 1606 传统题 文件IO:haircut 2000ms 256MiB 尝试: 0 已通过: 0 难度: 提高+/省选- 上传者: 标签>USACO赛事:open20来源:usaco.orgscoring:equal_test_cases二分差分

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 NN (1≤N≤1051\le N\le 10^5) strands of hair arranged in a line, and strand ii is initially AiA_i micrometers long (0≤Ai≤N0\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)(i,j) such that i<ji < j and Ai>AjA_i > A_j. For each of j=0,1,…,N−1j=0,1,\ldots,N-1, FJ would like to know the badness of his hair if all strands with length greater than jj are decreased to length exactly jj. (Fun fact: the average human head does indeed have about 10510^5 hairs!)

输入格式

The first line contains NN. The second line contains A1,A2,…,AN.A_1,A_2,\ldots,A_N.

输出格式

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

数据范围

Test case 2 satisfies N≤100.N\le 100. Test cases 3-5 satisfy N≤5000.N\le 5000. 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++).