#CSPJ202605D. 高楼视野

高楼视野

【题目描述】

城市里有 NN 栋高楼,从左到右依次编号为 1,2,,N1, 2, \ldots, N。第 ii 栋楼的高度为 HiH_i,且所有楼的高度互不相同。

对于每一栋楼 ii,我们想知道:从这栋楼向右看,能看到多少栋楼?具体来说,对于每个 ii,请计算满足以下条件的整数 jji<jNi < j \leq N)的数量:

  • 在楼 ii 和楼 jj 之间(不包括楼 ii 和楼 jj 本身),没有比楼 jj 更高的楼。

换句话说,楼 jj 是从楼 ii 向右看时“可见”的,因为中间没有任何楼挡住它。

【输入格式】

第一行包含一个整数 NN
第二行包含 NN 个整数 H1,H2,,HNH_1, H_2, \ldots, H_N,表示每栋楼的高度。

【输出格式】

输出一行,包含 NN 个整数 c1,c2,,cNc_1, c_2, \ldots, c_N,用空格分隔。其中 cic_i 表示从楼 ii 向右看能看到的楼的数量。

【样例 1】

5
2 1 4 3 5
3 2 2 1 0

【样例 1 解释】

  • 对于 i=1i=1(高度为 22):满足条件的 jj2,3,52, 3, 5,共 33 个。注意 j=4j=4 不满足条件,因为在楼 11 和楼 44 之间有楼 33(高度为 44),它比楼 44(高度为 33)更高,挡住了视线。
  • 对于 i=2i=2(高度为 11):满足条件的 jj3,53, 5,共 22 个。
  • 对于 i=3i=3(高度为 44):满足条件的 jj4,54, 5,共 22 个。
  • 对于 i=4i=4(高度为 33):满足条件的 jj55,共 11 个。
  • 对于 i=5i=5(高度为 55):右边没有楼了,所以数量为 00

【样例 2】

4
1 2 3 4
3 2 1 0

【样例 2 解释】

这是一个递增序列,每栋楼都能看到它右边的所有楼。

【样例 3】

10
1 9 6 5 2 7 10 4 8 3
2 3 3 3 2 1 2 1 1 0

【数据规模与约定】

  • 1N2×1051 \leq N \leq 2 \times 10^5
  • 1HiN1 \leq H_i \leq N
  • 对于任意 iji \neq j,有 HiHjH_i \neq H_j