LG#P5788. 【模板】单调栈

【模板】单调栈

P5788 【模板】单调栈

题目描述

\hspace{15pt}给定一个长度为 nn 的整数数列 a1,a2,…,ana_1,a_2,\dots,a_n。

\hspace{15pt}定义函数 f(i)f(i) 表示数列中第 ii 个元素之后、第一个严格大于 aia_i 的元素的下标,即

f(i)=min⁡{j∣i<j≦n, aj>ai}f(i) = \min\{j \mid i < j \leqq n,\ a_j > a_i\}

\hspace{15pt}若不存在满足条件的 jj,则规定 f(i)=0f(i)=0。请你求出 f(1),f(2),…,f(n)f(1),f(2),\dots,f(n)。

输入格式

\hspace{15pt}第一行输入一个整数 n(1≦n≦3×106)n \left(1 \leqq n \leqq 3 \times 10^6\right) 代表数列的长度。

\hspace{15pt}第二行输入 nn 个整数 $a_1,a_2,\dots,a_n \left(1 \leqq a_i \leqq 10^9\right)$ 代表数列中的元素。

输出格式

\hspace{15pt}在一行上输出 nn 个整数 f(1),f(2),…,f(n)f(1),f(2),\dots,f(n),相邻两个整数之间用一个空格分隔。

测试样例

5
1 4 2 3 5
2 5 4 5 0

样例 1 解释

\hspace{15pt}数列为 a={1,4,2,3,5}a=\{1,4,2,3,5\},依次计算每个 f(i)f(i):

∙ \hspace{23pt}\bullet\,当 i=1i=1 时,a1=1a_1=1,它后面第一个大于 11 的元素是 a2=4a_2=4,所以 f(1)=2f(1)=2;

∙ \hspace{23pt}\bullet\,当 i=2i=2 时,a2=4a_2=4,它后面的 a3=2a_3=2、a4=3a_4=3 都不大于 44,而 a5=5>4a_5=5>4,所以 f(2)=5f(2)=5;

∙ \hspace{23pt}\bullet\,当 i=3i=3 时,a3=2a_3=2,它后面第一个大于 22 的元素是 a4=3a_4=3,所以 f(3)=4f(3)=4;

∙ \hspace{23pt}\bullet\,当 i=4i=4 时,a4=3a_4=3,它后面第一个大于 33 的元素是 a5=5a_5=5,所以 f(4)=5f(4)=5;

∙ \hspace{23pt}\bullet\,当 i=5i=5 时,a5a_5 之后没有元素,所以 f(5)=0f(5)=0。

\hspace{15pt}因此输出 2,5,4,5,02,5,4,5,0。

6
3 1 4 1 5 9
3 3 5 5 6 0

提示

\hspace{15pt}对于 30%30\% 的数据,n≦100n \leqq 100;

\hspace{15pt}对于 60%60\% 的数据,n≦5×103n \leqq 5 \times 10^3;

\hspace{15pt}对于 100%100\% 的数据,1≦n≦3×1061 \leqq n \leqq 3 \times 10^6,1≦ai≦1091 \leqq a_i \leqq 10^9。