求m区间内的最小值

题目描述

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

输入输出格式

输入格式：

第一行两个数n，m。

第二行，n个正整数，为所给定的数列。

输出格式：

n行，第i行的一个数ai，为所求序列中第i个数前m个数的最小值。

输入输出样例

输入样例#1： 

6 27 8 1 4 3 2

输出样例#1： 

077113

说明

【数据规模】

m≤n≤2000000

ai​≤3×1e7

看到区间最小值，其实第一反应应该是ST表，但是看到了六次方的数据范围，显然ST表会爆空间，那么我们该怎么办呢？（如果没听说过ST表就当没看见吧）

我们再一次分析题意，发现这道题的区间大小是固定的，再一次坚定了不用ST表的决心。

那么，我们在这里引入一个新的数据结构：单调队列。

顾名思义，单调队列就是满足单调的队列（废话），那么每一次对队列进行修改的时候就要维护它的单调性。

我们不妨想一想，每当我们加入一个数i的时候，如果它前面的数j要比他大的话，那么j就被i完爆了（就是j从现在开始就再也不会成为最小值了，至于原因，简单来说三个字：时效性）。

因此，每当我们向队列里加一个元素时，就要判断前面的数有没有比他大的，将所有比他大的数都弹掉，再将他加入队列，即可维护单调性，所以队首元素就是最小值（显然）

但是，题目中还说了一个条件：并不是i前面的所有数，而是i前面的m个数，因此我们还需要记录每一个数字的编号（开一个结构体，队列类型定义为结构体），如果过时了就弹掉。

列举几个单调队列的常用代码：

#include<deque>　　头文件

deque<数据类型>队列名　　定义队列

队列名.empty()　　判断队列是否为空

队列名.front()　　调用首元素

队列名.back()　　调用尾元素

队列名.pop_front()　　弹出首元素

队列名.pop_back()　　弹出尾元素

最后，附上本题代码

1 #include
     
       2 #include
      
        3 using namespace std; 4 struct pot 5 { 6     int num,v; 7 }a[2000005]; 8 int ans[2000005]; 9 deque
       
        dq;10 int main()11 {12     int n,m;13     scanf("%d%d",&n,&m);14     for(int i=1;i<=n;i++)15     {16         scanf("%d",&a[i].v);17         a[i].num=i;18     }19     for(int i=2;i<=n+1;i++)20     {21         while(dq.empty()==0&&a[i-1].v<=dq.back().v)22         {23             dq.pop_back();24         }25         dq.push_back(a[i-1]);26         while(dq.front().num<=i-m-1)27         {28             dq.pop_front();29         }30         ans[i]=dq.front().v;31     }32     for(int i=1;i<=n;i++)33     {34         printf("%d\n",ans[i]);35     }36     return 0;37 }