求助线段树 80 分

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double db;

const int N=1e6+50;
const int M=1e6+50;

inline ll read(){
    ll x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}

ll ans[N<<2],a[N<<2];
ll lazy_add[N<<2];
ll maxn[N<<2];
ll minn[N<<2];
ll n,k;

ll ls (ll x) { return x<<1;}
ll rs (ll x) { return x<<1|1;}
ll c(ll x){
    if(x==0) return 0x7fffffff; else return x;
}
void push_up(ll p){
    ans[p]=ans[ls(p)]+ans[rs(p)];
    maxn[p]=max(maxn[ls(p)],maxn[rs(p)]);
    minn[p]=min(c(minn[ls(p)]),c(minn[rs(p)]));
}

void build(ll p,ll l,ll r){
    lazy_add[p]=0;
    if(l==r) {ans[p]=a[l];maxn[p]=a[l];minn[p]=a[l];return;}
    ll mid=(l+r)>>1;
    build(ls(p),l,mid);
    build(rs(p),mid+1,r);
    push_up(p);
}

ll query_max(ll nx,ll ny,ll l,ll r,ll p){
    ll res=-0x3f3f3f;
    if(nx<=l&&r<=ny) return maxn[p];
    ll mid=(l+r)>>1;
    if(nx<=mid) res=max(query_max(nx,ny,l,mid,ls(p)),res);
    if(ny>mid)  res=max(query_max(nx,ny,mid+1,r,rs(p)),res);
    return res;
}
ll query_min(ll nx,ll ny,ll l,ll r,ll p){
    ll res=0x3f3f3f3f;
    if(nx<=l&&r<=ny) return minn[p];
    ll mid=(l+r)>>1;
    if(nx<=mid) res=min(query_min(nx,ny,l,mid,ls(p)),res);
    if(ny>mid)  res=min(query_min(nx,ny,mid+1,r,rs(p)),res);
    return res;
}

int main()
{
    n=read(),k=read();
    for(ll i=1;i<=n;++i) a[i]=read();
    build(1,1,n);
    for(ll i=1;i<=n-k+1;++i){
        printf("%lld ",query_min(i,i+k-1,1,n,1));
    }
    printf("\n");
    for(ll i=1;i<=n-k+1;++i){
        printf("%lld ",query_max(i,i+k-1,1,n,1));
    }
    return 0;
}