[Codeforces 547B] Mike and Feet

开始水题目了qwq 感觉单调栈就是用来对某一元素求之后第一个大于或者小于它的元素的大小以及位置（单调栈数据类型可以设置为结构体，一个存位置一个存大小）

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
#include<map>
#define maxn 200010
#define ll long long
using namespace std;
int tail,n;
struct nod{
    ll num,pos;
}a[maxn],ddz[maxn];
ll ans[maxn],tmp[maxn];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i) {scanf("%lld",&a[i].num);a[i].pos=i;}
    for(int i=1;i<=n;++i){
        while(tail&&a[i].num<=ddz[tail].num) tail--;
        ddz[++tail]=a[i];
        tmp[i]=ddz[tail].pos-ddz[tail-1].pos-1;
    }
    tail=0;
    ddz[0].pos=n+1;
    for(int i=n;i;i--){
        while(tail&&a[i].num<=ddz[tail].num) tail--;
        ddz[++tail]=a[i];
        tmp[i]+=ddz[tail-1].pos-ddz[tail].pos;
    }
    for(int i=1;i<=n;++i)
        ans[tmp[i]]=max(ans[tmp[i]],a[i].num);
    for(int i=n-1;i;i--) {
        if(ans[i]<ans[i+1]) ans[i]=ans[i+1];
    }
    for(int i=1;i<=n;++i) cout<<ans[i]<<" ";
    return 0;
}