记录编号	315578	评测结果	AWAWWWWTTT
题目名称	[HZOI 2016]从零开始的序列	最终得分	20
用户昵称	sxysxy	是否通过	未通过
代码语言	C++	运行时间	3.028 s
提交时间	2016-10-05 16:15:02	内存使用	16.31 MiB

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cstdarg>
#include <list>
#include <queue>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <cctype>
using namespace std;
#define BT __attribute__((optimize("03")))
#define MAXN 200004
int data[MAXN];
int st[MAXN][19];
int f[MAXN];

int fast_read()
{
    int r;
    char ch;
    bool sig = false;
    while(ch = getchar())
    {
        if(ch >= '0' && ch <= '9')
        {
            r = ch^0x30;
            break;
        }else if(ch == '-')
            sig = true;
    }
    while(isdigit(ch = getchar()))
        r = (r<<3)+(r<<1)+(ch^0x30);
    if(sig)return -r;
    return r;
}

inline int ask(int l, int r)
{
    int k = 0;
    while((1<<(k+1)) <= r-l+1)
        k++;
    return min(st[l][k], st[r-(1<<k)+1][k]);
}

int main()
{
    freopen("sky_seq.in", "r", stdin);
    freopen("sky_seq.out", "w", stdout);
    int n;
    n = fast_read();
    int mn = log(n)+1;
    for(int i = 0; i < n; i++)
        data[i] = fast_read();
    for(int i = 0; i < n; i++)
        st[i][0] = data[i];
    for(int j = 1; (1<<j) <= n; j++)
        for(int i = 0; i + (1<<j)-1 < n; i++)
            st[i][j] = min(st[i][j-1] ,st[i+(1<<(j-1))][j-1]);
    for(int i = 1; i <= n; i++) //长度
    {
         int ans = -0x7ffffffe;
         for(int j = 0; j+i-1 < n; )  //起点
         {
            int k = ask(j, j+i-1);
            if(k > ans)
            {
                j++;
                ans = k;
            }
            else
            {
                int t = 0;
                while(j+(1<<t+1)+i-1 < n && ask(j+(1<<(t+1)), i) <= ans)
                    t++;
                j = j+(1<<t);
            }
         }
         printf("%d ", ans);
    }
    
    return 0;
}