WLQ567 @ 2016-11-14 19:55:07
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=1000000+100;
int n,k;
int a[maxn];
int read(){
int n=0,sign=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')sign=-1;c=getchar();}
while(c>='0'&&c<='9')n=n*10+c-'0',c=getchar();
return n*sign;
}
int mx[maxn][25],mi[maxn][25];
void init(){
for(int i=1;i<=n;i++)mx[i][0]=mi[i][0]=a[i];
int m=(int)(log(n*1.0)/log(2.0));
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
if(j+(1<<(i-1))<=n){
mx[j][i]=max(mx[j][i-1],mx[j+(1<<(i-1))][i-1]);
mi[j][i]=min(mi[j][i-1],mi[j+(1<<(i-1))][i-1]);
}
return ;
}
int rmqmax(int l,int r){
int m=(int)(log((r-l+1)*1.0)/log(2.0));
return max(mx[l][m],mx[r-(1<<m)+1][m]);
}
int rmqmin(int l,int r){
int m=(int)log(((r-l+1)*1.0)/log(2.0));
return min(mi[l][m],mi[r-(1<<m)+1][m]);
}
int main(){
n=read(),k=read();
for(int i=1;i<=n;i++)a[i]=read();
init();
for(int i=1;i<=n-k+1;i++)printf("%d ",rmqmin(i,i+k-1));
printf("\n");
for(int i=1;i<=n-k+1;i++)printf("%d ",rmqmax(i,i+k-1));
return 0;
}
by winmt @ 2016-11-14 20:43:54
写那么麻烦干什么,还用rmq?!
直接C++-STL-priority_queue建个大根堆和小根堆就过了~不会TLE的。