醉了酒的李白 @ 2018-12-24 13:21:02
#include<iostream>
using namespace std;
int n,k;
int log[1000];
int mx[1000100][15],mn[1000100][15];
//int a[1000100];
int z;
int main()
{
cin>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>mn[i][0];
mx[i][0]=mn[i][0];
}
log[0]=-1;
for(int i=1;i<=100;i++)
log[i]=log[i/2]+1;
//for(int i=1;i<=100;i++)
// cout<<log[i]<<" ";
for(int j=1;j<=10;j++)
for(int i=1;i+(1<<j)-1<=n;i++)
{
mx[i][j]=max(mx[i][j-1],mx[i+(1<<j-1)][j-1]);
mn[i][j]=min(mn[i][j-1],mn[i+(1<<j-1)][j-1]);
}
for(int i=1;i+k-1<=n;i++)
cout<<min(mn[i][log[k]],mn[i+k-(1<<(log[k]))][log[k]])<<" ";
cout<<endl;
for(int i=1;i+k-1<=n;i++)
cout<<max(mx[i][log[k]],mx[i+k-(1<<(log[k]))][log[k]])<<" ";
}
by _Sein @ 2018-12-24 13:34:51
这道题不是用单调队列嘛
by 醉了酒的李白 @ 2018-12-24 13:43:28
@lb2003 是的,但是dalao说st表也可以水过
by ikka @ 2018-12-28 15:41:19
第二维开到