「冥界の土地も有限よ、余計な霊魂は全て斬る！」
单调队列
单调队列是一种神奇的数据结构。
一般我们用来优化这一类决策有单调性的问题：
比如：一个元素很明显不可能进入决策的时候，我们可以用单调队列来做到 \(\text{O}(1)\) 的决策。
这里来一道题（来自WC2016 by 宋新波）
这里相当于是在保质期之内，求每一天最大能吃到的值。
这里考虑维护一个队列，队列当中单调不上升。
那么队头就是我们所想要的结果（最优）。
- Day1：
--------------
80
--------------
这里队头是80.
- Day2:
-------------
80 75
-------------
这里队头仍然是80.
- Day3
这里开始就要注意了，我们放入78，但是放进去之后就不满足条件了。
为什么？
不是因为后面小了就是前面大了（这里是单调不上升所以是这样，其他同理）。
不过我们一般考虑后面小了（从后面进队出队）。
那么在插入78 之前，我们就要弹出75 （从后方）
-------------
80 75(pop) --->
-------------
-------------
80 <------ 78(push)
-------------
-------------
80 78
-------------
此时队头仍然是 80。
这里我们不难看出，如果存在 \(a_i <a_j\)
那么 \(a_i\) 一定会被 \(a_j\) 替换掉。
因为 \(a_i\) 不仅时间靠前（更快过期），价值也不大。
所以 \(a_i\) 就是 冗杂的多余决策。
那么单调队列在维护的时候的意义就是去除这些冗杂的元素。
因为每个元素只会入队一次（所以要小心某些题的条件），所以 复杂度是 \(\text{O}(n)\) 的。
- Day 4
-------------
80 78 73
-------------
- Day 5
这里根据 Day3，我们需要把78,73弹出来让更好的 79 入队。
所以队列就变成了这样：
-------------
80 79
-------------
poped:78 73
但是注意！这里80过期了，所以要把80也弹出（从队头弹出）
那么就是这样的：
-------------
<---80 79
-------------
所以第五天就是 79 为最值。
那么我们就可以知道，在这道题使用单调队列时，要注意一下几点：
-
队列中始终单调
-
队首为最优情况
-
及时去除冗杂情况
那么我们每一次循环的时候，都检查一下队首是否过期还有新入队元素会不会造成更新就好了。
总结一下：也就是这样的
这里给出维护一个长度为 \(k\) 的滑动窗口中的最值的代码。
#include<bits/stdc++.h>
using namespace std;
const int si=1e6+10;
int n,k;
int a[si];
int q1[si],head1=1,tail1=0; //这样子赋值是为了让第一个元素能入队。
int q2[si],head2=1,tail2=0;
int ans[si][2]; //0->min 1->max
int main(){
scanf("%d%d",&n,&k);
for(register int i=1;i<=n;++i){
scanf("%d",&a[i]);
}
for(register int i=1;i<=n;++i){
while(head1<=tail1 && q1[head1]+k<=i) head1++;//排除队头过期
while(head1<=tail1 && a[i]<=a[q1[tail1]]) tail1--;//排除队尾冗杂。
q1[++tail1]=i;
while(head2<=tail2 && q2[head2]+k<=i) head2++;
while(head2<=tail2 && a[i]>=a[q2[tail2]]) tail2--;
q2[++tail2]=i;
ans[i][0]=a[q1[head1]],ans[i][1]=a[q2[head2]];//注意这里q存的是下标，所以要将其作为下标。
}
for(register int i=k;i<=n;++i){//k是因为它的区间长度已经固定，所以前面的那些长度不满足，要去掉。
printf("%d ",ans[i][0]);
}puts("");
for(register int i=k;i<=n;++i){
printf("%d ",ans[i][1]);
}
return 0;
}
在每道题使用单调队列之前需要看清题目的端点取舍和条件。
比如 求m区间内的最小值 那道题就是求 \([i-k-1,i)\) 的最小值.
所以说最好在用之前手玩一下数据。
单调队列优化DP
Example
题目描述
在幻想乡，琪露诺是以笨蛋闻名的冰之妖精。
某一天，琪露诺又在玩速冻青蛙，就是用冰把青蛙瞬间冻起来。但是这只青蛙比以往的要聪明许多，在琪露诺来之前就已经跑到了河的对岸。于是琪露诺决定到河岸去追青蛙。
小河可以看作一列格子依次编号为0到N，琪露诺只能从编号小的格子移动到编号大的格子。而且琪露诺按照一种特殊的方式进行移动，当她在格子i时，她只移动到区间[i+l,i+r]中的任意一格。你问为什么她这么移动，这还不简单，因为她是笨蛋啊。
每一个格子都有一个冰冻指数A[i]，编号为0的格子冰冻指数为0。当琪露诺停留在那一格时就可以得到那一格的冰冻指数A[i]。琪露诺希望能够在到达对岸时，获取最大的冰冻指数，这样她才能狠狠地教训那只青蛙。
但是由于她实在是太笨了，所以她决定拜托你帮它决定怎样前进。
开始时，琪露诺在编号0的格子上，只要她下一步的位置编号大于N就算到达对岸。
输入格式
第1行：3个正整数N, L, R
第2行：N+1个整数，第i个数表示编号为i-1的格子的冰冻指数A[i-1]
输出格式
一个整数，表示最大冰冻指数。保证不超过2^31-1
输入输出样例
输入
5 2 3
0 12 3 11 7 -2
输出
11
说明/提示
对于60%的数据：N <= 10,000
对于100%的数据：N <= 200,000
对于所有数据 -1,000 <= A[i] <= 1,000且1 <= L <= R <= N
这题明显的是一个线性DP。
首先我们考虑 60pts 的数据怎么做。
设 \(f[i]\) 表示Cirno走到第 \(i\) 个格子的时候可以取得的最大值。
那么很明显方程式这样子的：
\[f[i]=\max \{ f[j]+ice[i] \} ,(i \in [l,n],j \in [i-r,i-l]) \]转移应该是 \(\text{O}(n^2)\) 的。 60% 数据勉强过。
现在考虑对它进行优化。
仔细想想，我们每次更新都是这样子的。
你会发现 \([i-r,i-l]\) 这个区间的上下界是随 \(i\) 不断后移的（区间平移，具有单调性）
而且对于每一个决策它只会进入这个区间一次并且只出去一次（区间不会平移回来）。
所以我们想到了“滑动窗口” 这个东西。
那么就可以使用单调队列进行决策的优化。
我们首先维护队列里的单调性，保证队头一定是当前可以转移过来的状态的最优状态。
另外，当队头无法到达当前决策点 \(i\) 的时候，我们把队头出队。
这样子我们就做到了 \(\text{O}(1)\) 让每一次转移时都取最优值（并且这个状态是合法的）。
说白了就是使用单调队列代替 for 来决策。
注意，按照我的这种写法，单调队列维护的是 \([head,tail]\) 这个闭区间的元素。
Code:
#include<bits/stdc++.h>
using namespace std;
const int si=2e5+10;
int n,l,r;
int a[si];
int f[si];
int q[si],head=1,tail=0;
int main(){
scanf("%d%d%d",&n,&l,&r);
if(l>r) swap(l,r);
for(register int i=0;i<=n;++i){
scanf("%d",&a[i]);
}
memset(f,-0x3f,sizeof f);
int ans=-INT_MAX;//attention here
f[0]=0;//init
for(register int i=l;i<=n;++i){ start from 0,so the first point we can arrive is l.
while(head<=tail && q[head]<=(i-r-1)) head++;
while(head<=tail && f[q[tail]]<f[i-l]) tail--;
q[++tail]=i-l;
f[i]=f[q[head]]+a[i];
if(i+r>n) ans=max(f[i],ans); // reach the destination
}
printf("%d",ans);
return 0;
}
这时候就有人要问了，二维的怎么做？
也是同理。
这样子的转移（\([l,r]\) 随 \(j\) 平移） 都是可以的。
只是你需要根据题目要求判断一下什么时候出队，什么时候入队，什么时候决策。