AT_abc372_d [ABC372D] Buildings
题目描述
这里有 n 栋房子排成一排,从左往右依次编号为 1,2,…,n,第 i 栋房子的高度为 hi。
对于每个 i(1≦i≦n),请求出满足以下条件的整数 j 的数量:
∙i<j≦n;
∙在 i 与 j 之间(不含第 i 栋和第 j 栋)没有一栋房子比第 j 栋房子高。
也就是说,站在第 i 栋房子处向右看,若第 j 栋房子没有被它前面的某一栋房子挡住,就计入答案。
输入格式
第一行输入一个整数 n(1≦n≦2×105) 代表房子的数量。
第二行输入 n 个整数 $h_1, h_2, \dots, h_n \left(1 \leqq h_i \leqq n\right)$ 代表每栋房子的高度。保证 h1,h2,…,hn 两两不同。
输出格式
在一行上输出 n 个整数 c1,c2,…,cn,相邻两个整数之间用一个空格分隔。其中 ci 代表满足条件的 j 的数量。
测试样例
5
2 1 4 3 5
3 2 2 1 0
样例 1 解释
这 5 栋房子的高度依次为 2,1,4,3,5,逐个 i 分析如下:
∙当 i=1 时,j=2,3,5 满足条件。其中 j=4 不满足条件,因为第 1 栋与第 4 栋之间的第 3 栋房子高度为 4,比第 4 栋房子的高度 3 更高。因此 c1=3;
∙当 i=2 时,j=3,5 满足条件。其中 j=4 不满足条件,因为第 3 栋房子高度为 4,比第 4 栋房子更高。因此 c2=2;
∙当 i=3 时,j=4,5 满足条件。因此 c3=2;
∙当 i=4 时,j=5 满足条件。因此 c4=1;
∙当 i=5 时,不存在满足 i<j≦n 的 j,因此 c5=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
提示
由 1≦hi≦n 且 hi 两两不同可知,{h1,h2,…,hn} 一定是 1∼n 的一个排列。