4boy @ 2016-11-09 15:46:00
#include<iostream>
#include<cstdio>
#define maxn 10010000
#define INF 0x3f3f3f3f
#define ll long long int
#define lson x<<1,left,mid
#define rson (x<<1)|1,mid+1,right
using namespace std;
int n,k;
ll mx=-1,mn=INF;
int ans1[maxn],ans2[maxn],a[maxn];
struct Node
{
int l,r;
ll ma,mi;
}node[maxn*4];
void build(int x,int left,int right)
{
node[x].l=left;
node[x].r=right;
if(left==right)
{
node[x].ma=a[left];
node[x].mi=a[left];
return;
}
int mid=(left+right)>>1;
build(lson);
build(rson);
node[x].ma=max(node[x<<1].ma,node[(x<<1)|1].ma);
node[x].mi=min(node[x<<1].mi,node[(x<<1)|1].mi);
}
void quest(int x,int left,int right,int ql,int qr)
{
if(ql<=left && qr>=right)
{
mx=max(mx,node[x].ma);
mn=min(mn,node[x].mi);
return;
}
else if(left>qr || right<ql) return;
int mid=(left+right)>>1;
quest(lson,ql,qr);
quest(rson,ql,qr);
}
void work()
{
cin>>n>>k; k--;
for(int i=1;i<=n;i++)
cin>>a[i];
build(1,1,n);
for(int i=1;i<=n-k;i++)
{
quest(1,1,n,i,i+k);
ans1[i]=mn; ans2[i]=mx;
mn=INF; mx=-1;
}
}
void pt()
{
for(int i=1;i<=n-k;i++) cout<<ans1[i]<<" "; cout<<"\n";
for(int i=1;i<=n-k;i++) cout<<ans2[i]<<" ";
}
int main()
{
work();
pt();
return 0;
}
by 4boy @ 2016-11-09 15:48:34
MAXN那里去一个0=-=