wxwoo @ 2019-03-02 12:37:20

by wxwoo @ 2019-03-02 12:38:08

#include<cstdio>

#include<iostream>

using namespace std;

#define ls(x) x<<1

#define rs(x) x<<1|1

#define N 1000001

unsigned int n,m,k,a[N],big[N<<2],sml[N<<2]/*,tag[N<<2]*/;

void init()

{

    scanf("%d%d",&n,&k);

    m=n-k+1;

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

    {

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

    }

}

inline void pushup(int p)

{

    big[p]=max(big[ls(p)],big[rs(p)]);

    sml[p]=min(sml[ls(p)],sml[rs(p)]);

}

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

{

    //tag[p]=0;

    if(l==r)

    {

        big[p]=sml[p]=a[l];

        return;

    }

    int m=(l+r)>>1;

    build(ls(p),l,m);

    build(rs(p),m+1,r);

    pushup(p);

}

/*

inline void f(int p,int l,int r,int k)

{

    tag[p]=tag[p]+k;

    ans[p]=ans[p]+k*(r-l+1);

}

inline void pushdown(int p,int l,int r)

{

    int m=(l+r)>>1;

    f(ls(p),l,m,tag[p]);

    f(rs(p),m+1,r,tag[p]);

    tag[p]=0;

}

inline void update(int nl,int nr,int l,int r,int p,int k)

{

    if(nl<=l&&r<=nr)

    {

        ans[p]+=k*(r-l+1);

        tag[p]+=k;

        return;

    }

    pushdown(p,l,r);

    int m=(l+r)>>1;

    if(nl<=m)

        update(nl,nr,l,m,ls(p),k);

    if(m<nr)

        update(nl,nr,m+1,r,rs(p),k);

    pushup(p);

}

*/

int querymin(int qx,int qy,int l,int r,int p)

{

    int res=2147483647;

    if(qx<=l&&r<=qy)

        return sml[p];

    int m=(l+r)>>1;

    //pushdown(p,l,r);

    if(qx<=m)

        res=min(res,querymin(qx,qy,l,m,ls(p)));

    if(m<qy)

        res=min(res,querymin(qx,qy,m+1,r,rs(p)));

    return res;

} 

int querymax(int qx,int qy,int l,int r,int p)

{

    int res=0;

    if(qx<=l&&r<=qy)

        return big[p];

    int m=(l+r)>>1;

    //pushdown(p,l,r);

    if(qx<=m)

        res=max(res,querymax(qx,qy,l,m,ls(p)));

    if(m<qy)

        res=max(res,querymax(qx,qy,m+1,r,rs(p)));

    return res;

} 

int main()

{

    init();

    build(1,1,n);

    for(int i=1;i<=m;i++)

    {

        printf("%d ",querymin(i,i+k-1,1,n,1));

    }

    putchar('\n');

    for(int i=1;i<=m;i++)

    {

        printf("%d ",querymax(i,i+k-1,1,n,1));

    }

    return 0;

}

by wxy_god @ 2019-03-02 12:38:27

去你的刚学OI

by t162 @ 2019-03-02 12:38:38

去你的萌新

by aminoas @ 2019-03-02 12:38:55

刚学OI？

去你的萌新

by xunJason @ 2019-03-02 12:39:44

话说这题用单调队列最好吧

by wxwoo @ 2019-03-02 12:40:10

@Bambusoideae @我是一个垃圾

dalao别装弱啊...帮我看看错吗哪了qwqwq

by wxwoo @ 2019-03-02 12:43:01

我还是拿手机敲的线段树板子啊qwqwq

by wxy_god @ 2019-03-02 12:44:38

我真的不会线段树...

by AC_Automation @ 2019-03-02 12:46:06

建议学学正解单调队列。

线段树我觉得可能会T，毕竟常数大，复杂度也大

by xunJason @ 2019-03-02 12:47:12

ST表也行吧