原题传送门 求出每个点向左延伸到 l i l_i li，向右延伸到 r i r_i ri 表示 a i a_i ai是 a l i 到 a r i a_{l_i}到a_{r_i} ali到ari最小的 对于 a n s r i − l i + 1 = m a x ( a n s r i − l i + 1 , a i ) ans_{r_i-l_i+1}=max(ans_{r_i-l_i+1},a_i) ansri−li+1=max(ansri−li+1,ai) a n s i = m a x ( a n s i , a n s i + 1 ) ans_i=max(ans_i,ans_{i+1}) ansi=max(ansi,ansi+1)
l i , r i l_i,r_i li,ri用单调栈处理
Code：
#include <bits/stdc++.h> #define maxn 200010 using namespace std; int n, a[maxn], l[maxn], r[maxn], stk[maxn], ans[maxn]; inline int read(){ int s = 0, w = 1; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') w = -1; for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48); return s * w; } int main(){ n = read(); for (int i = 1; i <= n; ++i) a[i] = read(); int top = 0; for (int i = 1; i <= n; ++i){ while (top && a[stk[top]] > a[i]) r[stk[top--]] = i - 1; stk[++top] = i; } while (top) r[stk[top--]] = n; for (int i = n; i; --i){ while (top && a[stk[top]] > a[i]) l[stk[top--]] = i + 1; stk[++top] = i; } while (top) l[stk[top--]] = 1; for (int i = 1; i <= n; ++i) ans[r[i] - l[i] + 1] = max(ans[r[i] - l[i] + 1], a[i]); for (int i = n - 1; i; --i) ans[i] = max(ans[i], ans[i + 1]); for (int i = 1; i <= n; ++i) printf("%d ", ans[i]); return 0; }