zcmimi's blog
查看原题

点击跳转

记录每个点左边和右边第一个比它小的,就可以求出它能的贡献区间

#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
using namespace std;
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define dwn(i,s,t) for(int i=s;i>=t;i--)
#define clr(x,c) memset(x,c,sizeof(x))
int read(){
    int x=0;char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) x=x*10+c-'0',c=getchar();
    return x;
}
char sh[15];
void print(int x){
    int cnt=0;
    while(x) sh[++cnt]=x%10,x/=10;
    dwn(i,cnt,1) putchar(sh[i]+48);
    putchar(32);
}
const int nmax=2e5+5;
const int inf=0x7f7f7f7f;
int a[nmax],ans[nmax],l[nmax],r[nmax],q[nmax];
void maxs(int &a,int b){
    if(a<b) a=b;
}
int main(){
    int n=read();rep(i,1,n) a[i]=read();
    l[1]=1;int cur=1;q[1]=1;
    rep(i,2,n){
        while(a[q[cur]]>=a[i]&&cur) --cur;
        l[i]=q[cur]+1;q[++cur]=i;
    }
    r[n]=n;cur=1;q[1]=n;q[0]=n+1;
    dwn(i,n-1,1){
        while(a[q[cur]]>=a[i]&&cur) --cur;
        r[i]=q[cur]-1;q[++cur]=i;
    }
    rep(i,1,n) maxs(ans[r[i]-l[i]+1],a[i]);
    int tmp=0;
    dwn(i,n,1) maxs(ans[i],tmp),maxs(tmp,ans[i]);
    rep(i,1,n) print(ans[i]);printf("\n");
    return 0;
}
51nod 1437 迈克步
comment评论
Search
search