#P6278. [USACO20OPEN] Haircut G

[USACO20OPEN] Haircut G

题目描述

Farmer John 由于对整理他难以整平的头发感到疲惫,于是决定去理发。他有一排 NN 缕头发,第 ii 缕头发初始时长度为 AiA_i 微米(0AiN0\le A_i\le N)。理想情况下,他想要他的头发在长度上单调递增,所以他定义他的头发的“不良度”为逆序对的数量:满足 i<ji < jAi>AjA_i > A_j 的二元对 (i,j)(i,j)
对于每一个 j=0,1,,N1j=0,1,\ldots,N-1,Farmer John 想要知道他所有长度大于 jj 的头发的长度均减少到 jj 时他的头发的不良度。


(有趣的事实:人类平均确实有大约 10510^5 根头发!)

输入格式

输入的第一行包含 NN
第二行包含 A1,A2,,ANA_1,A_2,\ldots,A_N

输出格式

对于每一个 j=0,1,,N1j=0,1,\ldots,N-1,用一行输出 Farmer John 头发的不良度。


注意这个问题涉及到的整数大小可能需要使用 6464 位整数型存储(例如,C/C++ 中的“long long”)。

5
5 2 3 3 0
0
4
4
5
7

提示

样例解释:

输出的第四行描述了 Farmer John 的头发长度减少到 33 时的逆序对数量。
A=[3,2,3,3,0]A=[3,2,3,3,0] 有五个逆序对:A1>A2,A1>A5,A2>A5,A3>A5,A_1>A_2,\,A_1>A_5,\,A_2>A_5,\,A_3>A_5,A4>A5A_4>A_5


对于 100%100\% 的数据,1N1051\le N\le 10^5

1313 个测试点,其中 11 为样例,其余性质如下:

测试点 22 满足 N100N\le 100
测试点 353\sim 5 满足 N5000N\le 5000
测试点 6136\sim 13 没有额外限制。


出题人:Dhruv Rohatgi