单调队列

今天问了长者有关单调队列的知识，单调队列这种东西其实用途并不是特别的广泛，只是在处理区间上询问的时候比较管用，而且这种询问有限制，比如：

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

这种类似的题目，每次询问前m个数中最小的，显然暴力的话是O（n * m）的每个点枚举一遍m，就是这样，但是暴力显然会TLE，那有什么办法呢？

RMQ是可以的，但是有一个问题，就是MLE，2000000 * 20，会炸空间，线段树显然是可以的，但是还不是最优的。所以我们引出单调队列这种东西，解决序列上滑块的问题（m这个区间在序列上动来动去，就像是个滑块^_^）.

单调队列？

我们制作一个严格上升或下降的队列，它的队首是你处理当前区间的最大（最小）值，然后进行删除和加入的操作。

加入： 我们假设有8,1,2,3,7,9,6.这样的一个序列，我们想要一个单调上升的序列，这样就可以保证队首是最小的。我们加入元素的时候我们要存下每个值在原序列中的下标，因为，我们只有处理[i-m,i]这样的一个区间，如果队首元素的下标不在这个区间，显然就毫无意义了不。好，我们开始加入元素，我们每次添加元素，从队尾开始比较，直到找到比它小的数替换掉。

假设没有删除操作

第一次 :8

第二次：1（1 < 8 所以 我们替换掉8）

第三次：1,2.

第四次：1,2,3.

第五次：1,2,3,7.

第六次：1,2,3,7,9.

第七次：1,2,3,6.（跟7,9,比较都小，所以替换，尾指针直到6的位置）。

删除

删除其实很简单，我们比较队首的下标如果不在范围内直接删掉。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;#define REP(i,a,b) for(register int i = (a), i##_end_ = (b); i <= i##_end_ ; ++i)inline int read(){ char c = getchar();register int fg = 1,sum = 0; while(c < '0' || c > '9') { if(c == '-')fg = -1; c = getchar(); } while(c >= '0' && c <= '9') { sum =sum * 10 + c - '0'; c = getchar(); } return fg * sum;}const int maxn = 2000000+10;struct T{ int val,pos;};struct que{ int l,r; T a[maxn]; que(){l = 1, r = 0;} inline void putin(T x)//加入 { while(r >= l && a[r].val > x.val)r--; a[++r] = x; } inline void pop(int pos)//删除 { while(r >= l && a[l].pos < pos)l++; } void print() { for(int i=l;i<=r;i++) printf("%d ",a[i].val); printf("\n"); } inline int top() { return a[l].val;}}q;int n,m,f[maxn];int main(){ n = read(),m = read(); REP(i,1,n)f[i] = read(); puts("0"); q.putin((T){f[1],1}); REP(i,2,n) { q.print(); if(i-m>=0)q.pop(i-m); printf("%d\n",q.top()); q.putin((T){f[i],i}); } return 0;}