一个含有n项的数列(n<=2000000)，求出每一项前的m个数到它这个区间内的最小值。若前面的数不足m项则从第1个数开始，若前面没有数则输出0。
第一行两个数n，m。
第二行，n个正整数，为所给定的数列。
n行，第i行的一个数ai，为所求序列中第i个数前m个数的最小值。
题解：单调队列队首维护区间最值即可，注意输出的位置，必须弹掉出了查询区间的数后再输出，同时
注意到题干是作闭右开的区间，所以对于每次输出先找寻最小值，再用新元素进行更新维护单调性。
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> using namespace std; int n,m; struct node { int pos,data; }; node q[2000005]; int main() { scanf("%d%d",&n,&m); int head=1,tail=0; for(int i=1;i<=n;i++) { int x; scanf("%d",&x); while(head<=tail&&q[head].pos<(i-m)) head++; if(i==1) printf("0\n"); else printf("%d\n",q[head].data); while(head<=tail&&q[tail].data>=x) tail--; q[++tail].pos=i; q[tail].data=x; } return 0; }
原文：https://www.cnblogs.com/Hoyoak/p/11386240.html