Haircut

题目描述

厌倦了自己顽固的翘发，农夫约翰决定去理发。他有 $N$ ($1\le N\le 10^5$) 根头发按一条直线排列，第 $i$ 根头发的初始长度为 $A_i$ 微米（$0\le A_i\le N$）。理想情况下，他希望头发长度单调递增，因此他将头发的“糟糕程度（badness）”定义为逆序对（inversion）的数量：满足 $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

提示

输出的第 4 行描述的是当 FJ 的头发都被减少到长度 3 时的逆序对数量。此时 $A=[3,2,3,3,0]$ 有五个逆序对： $A_1>A_2,\,A_1>A_5,\,A_2>A_5,\,A_3>A_5,$ and $A_4>A_5$. SCORING: 测试点 2 满足 $N\le 100.$ 测试点 3-5 满足 $N\le 5000.$ 测试点 6-13 没有额外限制。 题目来源：Dhruv Rohatgi

标签: USACO|2020|Gold

来源

USACO|2020|Gold