#ABC372D. 建筑物

建筑物

AT_abc372_d [ABC372D] Buildings

题目描述

\hspace{15pt}这里有 nn 栋房子排成一排,从左往右依次编号为 1,2,…,n1, 2, \dots, n,第 ii 栋房子的高度为 hih_i。

\hspace{15pt}对于每个 i(1≦i≦n)i \left(1 \leqq i \leqq n\right),请求出满足以下条件的整数 jj 的数量:

∙ i<j≦n\hspace{23pt}\bullet\,i < j \leqq n;

∙ \hspace{23pt}\bullet\,在 ii 与 jj 之间(不含第 ii 栋和第 jj 栋)没有一栋房子比第 jj 栋房子高。

\hspace{15pt}也就是说,站在第 ii 栋房子处向右看,若第 jj 栋房子没有被它前面的某一栋房子挡住,就计入答案。

输入格式

\hspace{15pt}第一行输入一个整数 n(1≦n≦2×105)n \left(1 \leqq n \leqq 2 \times 10^5\right) 代表房子的数量。

\hspace{15pt}第二行输入 nn 个整数 $h_1, h_2, \dots, h_n \left(1 \leqq h_i \leqq n\right)$ 代表每栋房子的高度。保证 h1,h2,…,hnh_1, h_2, \dots, h_n 两两不同。

输出格式

\hspace{15pt}在一行上输出 nn 个整数 c1,c2,…,cnc_1, c_2, \dots, c_n,相邻两个整数之间用一个空格分隔。其中 cic_i 代表满足条件的 jj 的数量。

测试样例

5
2 1 4 3 5
3 2 2 1 0

样例 1 解释

\hspace{15pt}这 55 栋房子的高度依次为 2,1,4,3,52, 1, 4, 3, 5,逐个 ii 分析如下:

∙ \hspace{23pt}\bullet\,当 i=1i=1 时,j=2,3,5j=2, 3, 5 满足条件。其中 j=4j=4 不满足条件,因为第 11 栋与第 44 栋之间的第 33 栋房子高度为 44,比第 44 栋房子的高度 33 更高。因此 c1=3c_1=3;

∙ \hspace{23pt}\bullet\,当 i=2i=2 时,j=3,5j=3, 5 满足条件。其中 j=4j=4 不满足条件,因为第 33 栋房子高度为 44,比第 44 栋房子更高。因此 c2=2c_2=2;

∙ \hspace{23pt}\bullet\,当 i=3i=3 时,j=4,5j=4, 5 满足条件。因此 c3=2c_3=2;

∙ \hspace{23pt}\bullet\,当 i=4i=4 时,j=5j=5 满足条件。因此 c4=1c_4=1;

∙ \hspace{23pt}\bullet\,当 i=5i=5 时,不存在满足 i<j≦ni<j \leqq n 的 jj,因此 c5=0c_5=0。

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

提示

\hspace{15pt}由 1≦hi≦n1 \leqq h_i \leqq n 且 hih_i 两两不同可知,{h1,h2,…,hn}\{h_1, h_2, \dots, h_n\} 一定是 1∼n1 \sim n 的一个排列。