「冥界の土地も有限よ、余計な霊魂は全て斬る！」

单调队列

单调队列是一种神奇的数据结构。

一般我们用来优化这一类决策有单调性的问题：

比如：一个元素很明显不可能进入决策的时候，我们可以用单调队列来做到 \(\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 为最值。

那么我们就可以知道，在这道题使用单调队列时，要注意一下几点：

1. 队列中始终单调

2. 队首为最优情况

3. 及时去除冗杂情况

那么我们每一次循环的时候，都检查一下队首是否过期还有新入队元素会不会造成更新就好了。

总结一下：也就是这样的

这里给出维护一个长度为 \(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\) 个格子的时候可以取得的最大值。

那么很明显方程式这样子的：

转移应该是 \(\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\) 平移） 都是可以的。

只是你需要根据题目要求判断一下什么时候出队，什么时候入队，什么时候决策。