传统题 1000ms 256MiB

参差度

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

样例下载

题目描述

NN 棵树排成一排,第 ii 棵树的高度为 Hi(0≤Hi≤N)H_i (0 ≤ H_i ≤ N)。注意:可能有的树高度为 0.

树的高度参差不齐,显得并不美观。这里定义这排树的参差度为高度序列中含有的逆序对的数目。

现在要对一些树进行剪枝,降低他们的高度。

请你计算:对于每一个 j(0≤j≤N−1)j (0 ≤ j ≤ N-1),所有高度大于 jj 的树的高度均降低到 jj 时这排树的参差度。

输入格式

第一行:一个整数 NN。

第二行:NN 个整数,依次为 H1,H2,……,HNH_1,H_2,……,H_N。

输出格式

共 NN 行:每行一个整数,依次表示对于每一个 j(0≤j≤N−1)j (0 ≤ j ≤ N-1),所有高度大于 jj 的树的高度均降低到 jj 时这排树的参差度。

样例输入

5
5 2 3 3 0

样例输出

0
4
4
5
7

数据范围

大约 15%15\% 的数据满足 N≤100N ≤ 100。

大约 25%25\% 的数据满足 N≤5000N ≤ 5000。

100%100\% 的数据,1≤N≤1051 ≤ N ≤ 10^5,0≤Hi≤N0 ≤ H_i ≤ N

20250317

未参加
状态
已结束
规则
OI
题目
5
开始于
2025-3-17 8:30
结束于
2025-3-17 12:00
持续时间
3.5 小时
主持人
参赛人数
6