例题

LuoguP1440题目描述

一个含有n项的数列(n<=2000000)，求出每一项前的m个数到它这个区间内的最小值。若前面的数不足m项则从第1个数开始，若前面没有数则输出0。

---------------------------------------------------------------------------------------------------------

裸单调队列

front-tail闭区间

q保存的是a数组中下标

1.更新区间长度

while(q[front]

2.插入新元素

while(a[q[tail]]>a[i]&&tail>=front) tail--;q[++tail]=i;

 

#include
     
      #include 
      
       #include 
       
        using namespace std;const int N=2000005;inline int read(){    char c=getchar(); int x=0,f=1;    while(c<'0'||c>'9'){
   if(c=='-')f=-1;c=getchar();}    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}    return x*f;}int n,m,a[N];int q[N],front=1,tail=0;int main(){    n=read();m=read();    for(int i=1;i<=n;i++) a[i]=read();        for(int i=1;i<=n;i++){        while(q[front]
        
         a[i]&&tail>=front) tail--;        q[++tail]=i;    }}