P5788 【模板】单调栈

P5788 【模板】单调栈

传送门
题目描述

给出项数为 \(n\) 的整数数列 \(a_{1 \dots n}\)。
定义函数 \(f(i)\) 代表数列中第 \(i\) 个元素之后第一个大于 \(a_i\) 的元素的下标，即 \(f(i)=\min_{i a_i} \{j\}\)。若不存在，则 \(f(i)=0\)。
试求出 \(f(1\dots n)\)。
输入格式

第一行一个正整数 \(n\)。
第二行 \(n\) 个正整数 \(a_{1\dots n}\)。
输出格式

一行 \(n\) 个整数表示 \(f(1), f(2), \dots, f(n)\) 的值。
样例 #1

样例输入 #1

1. 5
2. 1 4 2 3 5

复制代码

样例输出 #1

1. 2 5 4 5 0

复制代码

提示

【数据规模与约定】
对于 \(30\%\) 的数据，\(n\leq 100\)；
对于 \(60\%\) 的数据，\(n\leq 5 \times 10^3\) ；
对于 \(100\%\) 的数据，\(1 \le n\leq 3\times 10^6\)，\(1\leq a_i\leq 10^9\)。
前要芝士：单调栈

什么是单调栈：

单调栈：顾名思义，单调栈即满足单调性的栈结构。
简单来说，就是栈内的数一直保持递增或递减的关系。
实现：

插入: 每次插入时为保证栈内递增或递减，我们将栈顶的元素不断与将插入的数进行比较，如果不能符合数字插入后保持递增或递减，就将栈顶元素删除。这样可以有效保证栈内保持单调性，这就是单调队列的插入操作。
我们可以使用如下代码模拟插入(以单调递增为例)：
[code]scanf("%d")while(!q.empty()&&q.top()