WydnksqhbD @ 2024-01-04 15:49:30
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e6+10;
int n,m;
int a[N],RMQ[N][21];
void ST()
{
for(int i=1;i<=n;i++)
{
scanf("%d",&RMQ[i][0]);
}
for(int j=1;j<=(int)(log(n)/log(2));j++)
{
for(int i=1;i+(1<<j)-1<=n;i++)
{
RMQ[i][j]=min(RMQ[i][j-1],RMQ[i+(1<<j-1)][j-1]);
}
}
return;
}
int ask(int l,int r)
{
int x=(int)(log(r-l+1)/log(2));
return min(RMQ[l][x],RMQ[r-(1<<x)+1][x]);
}
int main()
{
scanf("%d %d",&n,&m);
ST();
printf("0\n");
for(int i=2;i<=n;i++)
{
int left=i-m,right=i-1;
if(left<1)
{
left=1;
}
printf("%lld\n",ask(left,right));
}
return 0;
}
by xiaoshumiao @ 2024-01-04 16:05:04
@WydnksqhbD 您好,此题正解是单调队列。MLE 的原因是
by WydnksqhbD @ 2024-01-04 16:09:22
@xiaoshumiao 如果我不会单调队列怎么办。。。
by xiaoshumiao @ 2024-01-04 16:10:33
@WydnksqhbD 学。
by WydnksqhbD @ 2024-01-04 16:10:56
@xiaoshumiao 6