/*

     题意：对于长度为x的子序列，每个序列存放为最小值，输出长度为x的子序列的最大值

     set+线段树：线段树每个结点存放长度为rt的最大值，更新：先升序排序，逐个添加到set中

                 查找左右相邻的位置，更新长度为r - l - 1的最大值，感觉线段树结构体封装不错！

     详细解释：http://blog.csdn.net/u010660276/article/details/46045777

     其实还有其他解法，先掌握这种:)

 */

 #include <cstdio>

 #include <algorithm>

 #include <iostream>

 #include <iostream>

 #include <cstring>

 #include <set>

 using namespace std;

 typedef long long ll;

 #define lson l, mid, rt << 1

 #define rson mid + 1, r, rt << 1 | 1

 const int MAXN = 2e5 + ;

 const int INF = 0x3f3f3f3f;

 struct A

 {

     int v, id;

     bool operator < (const A &a) const

     {

         return v < a.v;

     }

 }a[MAXN];

 struct SegmentTree

 {

     int add[MAXN << ];

     int mx[MAXN << ];

     void push_down(int rt)

     {

         if (add[rt])

         {

             add[rt<<] = add[rt<<|] = add[rt];

             mx[rt<<] = mx[rt<<|] = add[rt];

             add[rt] = ;

         }

     }

     void build(int l, int r, int rt)

     {

         add[rt] = mx[rt] = ;

         if (l == r)    return ;

         int mid = (l + r) >> ;

         build (lson);    build (rson);

     }

     void updata(int ql, int qr, int c, int l, int r, int rt)

     {

         if (ql <= l && r <= qr)    {mx[rt] = c; add[rt] = c;    return ;}

         push_down (rt);

         int mid = (l + r) >> ;

         if (ql <= mid)    updata (ql, qr, c, lson);

         if (qr > mid)    updata (ql, qr, c, rson);

     }

     int query(int x, int l, int r, int rt)

     {

         if (l == r)    return mx[rt];

         push_down (rt);

         int mid = (l + r) >> ;

         if (x <= mid)    return query (x, lson);

         return query (x, rson);

     }

 }tree;

 int ans[MAXN];

 int main(void)        //Codeforces Round #305 (Div. 2) D. Mike and Feet

 {

     int n;

     while (scanf ("%d", &n) == )

     {

         for (int i=; i<=n; ++i)

         {

             scanf ("%d", &a[i].v);    a[i].id = i;

         }

         sort (a+, a++n);

         tree.build (, n, );

         set<int> S;    S.insert ();    S.insert (n + );

         set<int>::iterator it;

         for (int i=; i<=n; ++i)

         {

             int l, r;

             it = S.lower_bound (a[i].id);

             r = *it; it--; l = *it;

             if (r - l -  >= )    tree.updata (, r-l-, a[i].v, , n, );

             S.insert (a[i].id);

         }

         for (int i=; i<=n; ++i)

             ans[i] = tree.query (i, , n, );

         for (int i=; i<=n; ++i)

             printf ("%d%c", ans[i], (i==n) ? '\n' : ' ');

     }

     return ;

 }

 /*

 10

 1 2 3 4 5 4 3 2 1 6

 */

 /*

     jinye的解法：原理一样，找到最小值是a[i]的最长区间，用l[],r[]记录左右端点的位置

                 比线段树快多了:)

 */

 #include <cstdio>

 #include <iostream>

 #include <algorithm>

 #include <cstring>

 #include <cmath>

 using namespace std;

 const int MAXN = 2e5 + ;

 const int INF = 0x3f3f3f3f;

 int a[MAXN], l[MAXN], r[MAXN], ans[MAXN];

 int main(void)        //Codeforces Round #305 (Div. 2) D. Mike and Feet

 {

     int n;

     while (scanf ("%d", &n) == )

     {

         memset (ans, , sizeof (ans));

         for (int i=; i<=n; ++i)

         {

             scanf ("%d", &a[i]);

             l[i] = r[i] = i;

         }

         for (int i=; i<=n; ++i)

         {

             while (l[i] >  && a[i] <= a[l[i]-])    l[i] = l[l[i]-];

         }

         for (int i=n; i>=; --i)        //倒过来回超时

         {

             while (r[i] < n && a[i] <= a[r[i]+])    r[i] = r[r[i]+];

         }

         for (int i=; i<=n; ++i)

         {

             int x = r[i] - l[i] + ;

             ans[x] = max (ans[x], a[i]);

         }

         for (int i=n-; i>=; --i)        //可能范围扩展的太厉害了

         {

             ans[i] = max (ans[i], ans[i+]);

         }

         for (int i=; i<=n; ++i)

             printf ("%d%c", ans[i], (i==n) ? '\n' : ' ');

     }

     return ;

 }

数组效率更高