[Usaco2020 Open]Haircut

内存限制：512 MiB 时间限制：10 Sec

疲于对付他难以整平的头发，FarmerJohn决定去理发。他有一排N（1≤N≤10^5）缕头发，第i缕头发初始时长度为Ai微米（0≤Ai≤N）。理想情况下，他想要他的头发在长度上单调递增，所以他定义他的头发的“不良度”为逆序对的数量：满足i<j及Ai>Aj的二元对(i,j)。

对于每一个j=0,1,…,N−1，FJ想要知道他所有长度大于j的头发的长度均减少到j时他的头发的不良度。（有趣的事实：人类平均确实有大约10^5根头发！）

输入的第一行包含 N。

第二行包含 A1,A2,…,AN。

对于每一个 j=0,1,…,N−1，用一行输出 FJ 头发的不良度。

注意这个问题涉及到的整数大小可能需要使用 64 位整数型存储

（例如，C/C++ 中的“long long”）。


			5

5 2 3 3 0


			0

4

4

5

7

输出的第四行描述了 FJ 的头发长度减少到 3 时的逆序对数量。

A=[3,2,3,3,0] 有五个逆序对：

A1>A2,A1>A5,A2>A5,A3>A5, 和 A4>A5。

BZPRO Powered by Remmina.
Github Repository

#5570. [Usaco2020 Open]Haircut