Luogu P5788 【模板】单调栈

题目背景

模板题，无背景。

2019.12.12 更新数据，放宽时限，现在不再卡常了。

题目描述

给出项数为 $a_{1 dots n}a1…n。$

定义函数 $a_iai 的元素的下标，即 f(i)=min_{i<jleq n, a_j > a_i} {j}f(i)=mini<j≤n,aj>ai{j}。若不存在，则 f(i)=0f(i)=0。$

试求出

输入格式

第一行一个正整数

第二行 $a_{1dots n}a1…n。$

输出格式

一行

输入输出样例

输入 #1

5
1 4 2 3 5

输出 #1

2 5 4 5 0

说明/提示

【数据规模与约定】

对于 $30\%30% 的数据，nleq 100n≤100；$

对于 $60\%60% 的数据，nleq 5 imes 10^3n≤5×103 ；$

对于 $100\%100% 的数据，1 le nleq 3 imes 10^61≤n≤3×106，1leq a_ileq 10^91≤ai≤109。$

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <stack>
 5 using namespace std;
 6 
 7 const int N = 3000001;
 8 int n;
 9 int a[N], f[N];
10 
11 
12 int main(){
13     scanf("%d", &n);
14     for(int i = 1; i <= n; i++){
15         scanf("%d", &a[i]);
16     }
17     stack<int> s;
18     for(int i = n; i >= 1; i--){
19         while(!s.empty() && a[s.top()] <= a[i]) s.pop();
20         if(s.empty()){
21             f[i] = 0;
22         }else f[i] = s.top();
23         s.push(i);
24     }
25     for(int i = 1; i <= n; i++) printf("%d ", f[i]);
26 
27 
28 
29     return 0;
30 }