题目描述
一个含有n项的数列(n<=2000000)，求出每一项前的m个数到它这个区间内的最小值。若前面的数不足m项则从第1个数开始，若前面没有数则输出0。
输入输出格式
输入格式：
第一行两个数n，m。
第二行，n个正整数，为所给定的数列。
输出格式：
n行，第i行的一个数ai，为所求序列中第i个数前m个数的最小值。
输入输出样例
输入样例#1：
6 2
7 8 1 4 3 2
输出样例#1：
0
7
7
1
1
3
说明
【数据规模】
m≤n≤2000000
单调队列的裸题。
注意判断好队列里面元素的数量
维护递增序列
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
using namespace std;
int h=,t=;
int a[];
struct node
{
int q[];
int size()
{
return t-h;
}
void popt()
{
q[t]=;
t--;
}
void poph()
{
h++;
}
int front()
{
return q[h];
} void push(int x)
{
if(a[x]>=a[q[t]])
{
t++;
q[t]=x;
}
else
{
while(a[x]<a[q[t]]&&t>=h)
{
q[t]=;
t--;
}
t++;
q[t]=x;
} }
}que;
int main()
{
int n,m,x;
scanf("%d%d",&n,&m);
que.q[]=;
for(int i=;i<=n;i++)
{ scanf("%d",&x);
a[i]=x; if(i==)
{printf("0\n");
continue;} printf("%d\n",a[que.front()]); if(que.front()<=i-m)
que.poph(); que.push(i);
}
return ;
}