3392. [USACO20 Open Gold]Haircut

【题目描述】

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

对于每一个 $j=0,1,\ldots,N-1$，FJ 想要知道他所有长度大于 $j$ 的头发的长度均减少到 $j$ 时他的头发的不良度。

(有趣的事实：人类平均确实有大约 $10^5$ 根头发！)

【输入格式】

输入的第一行包含 $N$。

第二行包含 $A_1,A_2,\ldots,A_N$。

【输出格式】

对于每一个 $j=0,1,\ldots,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]$ 有五个逆序对：$A_1>A_2,\,A_1>A_5,\,A_2>A_5,\,A_3>A_5,$ 和 $A_4>A_5$。

【提示】

对于$ 15\% $的测试数据(测试点$ 1 \sim 2 $)，满足$ N \le 100 $。

对于$ 38\% $的测试数据(测试点$ 1 \sim 5 $)，满足$ N \le 5 \times 10^3 $。

对于$ 100\% $的测试数据，均满足上文所给出的数据规模。

【来源】

USACO 美国公开赛 Gold 组