Haircut

提交数: 4, 通过率: 25%, 平均分: 34.5

题目描述:

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

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

（有趣的事实：人类平均确实有大约 105 根头发！）

输入格式:

输入的第一行包含 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。

测试点性质：
  • 测试点 2 满足 N≤100。
  • 测试点 3-5 满足 N≤5000。
  • 测试点 6-13 没有额外限制。
时间限制: 1000ms
空间限制: 256MB

来源: USACO 2020 OPEN Gold