P5788 【模板】单调栈
题目描述
给定一个长度为 n 的整数数列 a1,a2,…,an。
定义函数 f(i) 表示数列中第 i 个元素之后、第一个严格大于 ai 的元素的下标,即
f(i)=min{j∣i<j≦n, aj>ai}
若不存在满足条件的 j,则规定 f(i)=0。请你求出 f(1),f(2),…,f(n)。
输入格式
第一行输入一个整数 n(1≦n≦3×106) 代表数列的长度。
第二行输入 n 个整数 $a_1,a_2,\dots,a_n \left(1 \leqq a_i \leqq 10^9\right)$ 代表数列中的元素。
输出格式
在一行上输出 n 个整数 f(1),f(2),…,f(n),相邻两个整数之间用一个空格分隔。
测试样例
5
1 4 2 3 5
2 5 4 5 0
样例 1 解释
数列为 a={1,4,2,3,5},依次计算每个 f(i):
∙当 i=1 时,a1=1,它后面第一个大于 1 的元素是 a2=4,所以 f(1)=2;
∙当 i=2 时,a2=4,它后面的 a3=2、a4=3 都不大于 4,而 a5=5>4,所以 f(2)=5;
∙当 i=3 时,a3=2,它后面第一个大于 2 的元素是 a4=3,所以 f(3)=4;
∙当 i=4 时,a4=3,它后面第一个大于 3 的元素是 a5=5,所以 f(4)=5;
∙当 i=5 时,a5 之后没有元素,所以 f(5)=0。
因此输出 2,5,4,5,0。
6
3 1 4 1 5 9
3 3 5 5 6 0
提示
对于 30% 的数据,n≦100;
对于 60% 的数据,n≦5×103;
对于 100% 的数据,1≦n≦3×106,1≦ai≦109。