单调队列

单调队列概述

定义

顾名思义，单调队列是队列内元素为单调递增或递减的队列。

单调队列的特点

单调队列内的元素满足单调性，队列为双端队列，$\text{STL}$ 提供了类模板 $\text{deque}$ 。由于 $\text{deque}$ 速度较慢，一般用数组模拟双端队列。

维护方式

通过双端队列头和尾的进出维护队列内元素的单调性。有删除队头、删除队尾、将元素推入队列三种操作。
维护队列内元素的单调性的本质是，每次操作都将没有潜力的元素从队列中去除，而将有潜力的元素放入队列。因此单调队列的作用就是用来保存一段区间内有潜力的元素。有潜力的元素是指将来可能满足具体问题条件或者能够成为最优解的元素。一般来说，新产生的元素都是有潜力的，可以毫不犹豫地将新产生的元素加入队列中，而只考虑是否要进行删除队头和删除队尾的操作。有句俗语称：比你晚来的还比你强，那你必定就没希望了。因此，如果后遍历到的元素潜力较之于队尾更大，需要果断将队尾删除。
当然，执行删除队头和删除队尾两种操作的条件需要具体问题具体分析。具体问题具体分析，是马克思主义活的灵魂。

单调性定义的扩展

一般在单调队列中存放的是原序列中对应元素的序号。假设原序列为 $a=[1,3,-1,-3,5,-9,7]$，可以有一个单调递减队列为 $q=[3,4,6]$，因为 $a[3]>a[4]>a[6]$ 。

例题

POJ 2823 Sliding Window $\looparrowright$

Description

An array of size $n ≤ 10^6$ is given to you. There is a sliding window of size $k$ which is moving from the very left of the array to the very right. You can only see the $k$ numbers in the window. Each time the sliding window moves rightwards by one position. Following is an example: The array is $[1, 3, -1, -3 ,5, 3, 6, 7]$ , and $k$ is $3$.

Window position	Minimum value	Maximum value
$[1,3,-1,]-3,5,3,6,7$	$-1$	$3$
$1,[3,-1,-3,]5,3,6,7$	$-3$	$3$
$1,3,[-1,-3,5,]3,6,7$	$-3$	$5$
$1,3,-1,[-3,5,3,]6,7$	$-3$	$5$
$1,3,-1,-3,[5,3,6,]7$	$3$	$6$
$1,3,-1,-3,5,[3,6,7]$	$3$	$7$

Your task is to determine the maximum and minimum values in the sliding window at each position.

Input

The input consists of two lines. The first line contains two integers $n$ and $k$ which are the lengths of the array and the sliding window. There are $n$ integers in the second line.

Output

There are two lines in the output. The first line gives the minimum values in the window at each position, from left to right, respectively. The second line gives the maximum values.

Sample Input

8 3
1 3 -1 -3 5 3 6 7

Sample Output

-1 -3 -3 -3 3 3
3 3 5 5 6 7

Translation

有一个长为 $n$ 的序列 $a$，以及一个大小为 $k$ 的窗口。现在这个从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最大值和最小值。

Idea

单调队列经典入门题：滑动窗口。
维护定长为 $k $ 的区间最值。
考虑维护一个单调递增队列 $q$ ，$q$ 中存放 $a $ 中对应元素的序号，队头所对应元素即为区间内最小值。
下面来用样例模拟维护单调递增队列的过程。整个过程基于循环 $\text{for }i\ \leftarrow\ 1\text{ to }n$ ，$i$ 代表窗口的最右端，时间复杂度为 $O(n)$。 要时刻记住单调队列的作用就是用来保存一段区间内有潜力的元素。
1.当遍历至 $a_1=1$ ，由于此时 $q$ 中没有元素，我们直接令 $a_1$ 进队。此时 $q=[1]$ 。
2.当遍历至 $a_2=3$，虽然 $a_1<a_2$，但是 $a_2$ 是有可能（有潜力）成为区间最小值的（当 $a_3>a_2$ 且 $a_4>a_2$ 时）。因此令 $a_3$ 进队。此时 $q=[1,3]$ 。
3.当遍历至 $a_3=-1$，队尾元素 $3$ 比 $-1$ 大，那么意味着只要 $-1$ 进队（即 $-1$ 被窗户框住），$3$ 在有生之年内（从被窗户框住到划出窗户前）必定成为不了最小值。所以，$3$ 从队尾出队。同理，$1$ 从队尾出队。最后 $-1$ 进队，此时 $q=[-1]$ 。
4.当遍历至 $a_4=-3 $，同上面分析，$-1>-3$，$-1$ 从队尾出队, $-3$ 进队。此时 $q=[-3]$。
5.当遍历至 $a_5=5$，$5$ 还是有潜力的，因此 $5$ 进队。此时 $q=[-3,5]$ 。
6.当遍历至 $a_6=3$，由于 $3<5$ ，于是 $5$ 出队；此时队尾 $-3<3$ ，因此保留 $-3$ ，$3$ 也进队。此时 $q=[-3,3]$。
7.当遍历至 $a_7=6$，因为队尾 $3<6$ ，所以 $6$ 直接进队。因为此时队头 $-3$ 已经在窗口之外，$-3$ 从队头出队。此时 $q=[3,6]$
8.当遍历至 $a_8=7$，因为队尾 $6<7$ ，因此 $7 $ 直接进队。此时 $q=[3,6,7]$ 。
综上所述，我们维护了一个单调递增的队列，队头即为长度为 $k$ 的区间内的最小值，删除队尾的条件是队尾元素已经没有成为最小值的可能，删除队头的条件是，队头元素已经在滑动窗口外部。
关于单调递减队列与单调递增队列类似。
事实上，一般只在队列内存对应元素的索引，具体可以看代码。

Code

#include<iostream>
#include<cstdio>
#define N 1000003
using namespace std;
int n,k;
int q[N];//声明单调队列
int a[N];
int main()
{
	cin>>n>>k;
	int i;
	for(i=1;i<=n;i++) scanf("%d",a+i);
	int head=1,tail=0;
	//to choose the more potential one
	for(i=1;i<=n;i++)//维护单调递增队列
	{
		/*大于等于新出现元素的元素全都从队尾出队
		由于q中存的是索引，比较时要调用a[q[tail]]*/
		while(head<=tail&&a[q[tail]]>=a[i]) tail--;
		q[++tail]=i;//新元素的索引进队
		while(q[head]<i-k+1) head++;//窗口外的元素从队头出队
		if(i>=k) printf("%d ",a[q[head]]);//输出队头
	}
	putchar('\n');
	/*维护单调递减队列
	与单调递增队列同理*/
	head=1,tail=0;
	for(i=1;i<=n;i++)
	{
		while(head<=tail&&a[q[tail]]<=a[i]) tail--;
		q[++tail]=i;
		while(q[head]<i-k+1) head++;
		if(i>=k) printf("%d ",a[q[head]]);
	}
	return 0;
}

FZU 1894 志愿者选拔 $\looparrowright$

Problem Description

世博会马上就要开幕了，福州大学组织了一次志愿者选拔活动。
参加志愿者选拔的同学们排队接受面试官们的面试。参加面试的同学们按照先来先面试并且先结束的原则接受面试官们的考查。
面试中每个人的人品是主要考查对象之一（提高人品的方法有扶老奶奶过街，不闯红灯等）。
作为主面试官的 $\text{John}$ 想知道当前正在接受面试的同学队伍中人品值最高的是多少。于是他请你帮忙编写一个程序来计算。

Input

输入数据第一行为一整数 $T$，表示有 $T$ 组输入数据。
每组数据第一行为 ”START” ，表示面试开始。
接下来的数据中有三种情况

	输入	含义
1	$\text{C}$ $NAME$ $RP_{VALUE}$	名字为 $NAME$ 的人品值为 $RP_{VALUE}$ 的同学加入面试队伍（名字长度不大于 $5$，$0 \le RP_{VALUE}\le 1000000000$）。
2	$\text{G}$	排在面试队伍最前面的同学面试结束离开考场。
3	$\text{Q}$	主面试官 $\text{John}$ 想知道当前正在接受面试的队伍中人品最高的值是多少。

最后一行为”END”，表示所有的面试结束，面试的同学们可以依次离开了。
所有参加面试的同学总人数不超过 $1000000$ 。

Output

对于每个询问 $\text{Q}$ ，输出当前正在接受面试的队伍中人品最高的值，如果当前没有人正在接受面试则输出 $-1$。

Sample Input

2
START
C Tiny 1000000000
C Lina 0
Q
G
Q
END
START
Q
C ccQ 200
C cxw 100
Q
G
Q
C wzc 500
Q
END

Sample Output

1000000000
0
-1
200
100
500

Hint

数据较大建议使用 $\text{scanf}$ 和 $\text{printf}$ 不推荐使用 $\text{STL}$ 。

Idea

面试时每个人进出的顺序符合队列的所有操作，定义这个队伍为 $Q$，每次新出现一名同学都令其无条件进队。
考虑维护一个单调递减的队列 $q$ ，其中储存 $Q$ 中元素的序号，每次查询时输出队头代表的元素。
当读取到字符 $\text{G}$ ，需要将 $Q$ 的队头删除。若 $q$ 的队头就是 $Q$ 的队头，那么 $q$ 的队头就会被一并删除。

Code

#include<iostream>
#include<cstdio>
#define N 1000004
using namespace std;
inline int read()
{
	int X=0; bool flag=1; char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-') flag=0; ch=getchar();}
	while(ch>='0'&&ch<='9') {X=(X<<1)+(X<<3)+ch-'0'; ch=getchar();}
	if(flag) return X;
	return ~(X-1);
}
inline void write(int X)
{
	if(X<0) {X=~(X-1); putchar('-');}
	if(X>9) write(X/10);
	putchar(X%10+'0');
}
int q[N];
char opt[10];
struct node
{
	char name[10];
	int val;
}Q[N];
int main()
{
	int _;
	for(cin>>_;_;_--)
	{
		int head=1,tail=0;
		int i=0;//Q的队尾
		int first=1;//Q的队头
		while(~scanf("%s",opt))//读取操作
		{
			if(opt[0]=='S') continue;
			else if(opt[0]=='C')
			{
				i++;
				scanf("%s",Q[i].name);
				Q[i].val=read();
				//to choose the more potential one 
				/*后来的Q[q[tail]].val更大
				队列中小于Q[q[tail]].val的元素都不可能成为最大值*/
				while(head<=tail&&Q[i].val>=Q[q[tail]].val) tail--;
				q[++tail]=i;//进队
			}
			else if(opt[0]=='Q') 
			{
				if(head<=tail)//单调队列中有元素 
				{
					write(Q[q[head]].val);
					putchar('\n');
				}
				else puts("-1");
			}
			else if(opt[0]=='G')
			{
				if(q[head]==first) head++;//一并删除q的队头
				first++;
			}
			else break;
		}
	}
	return 0;
}

HDU 3530 Subsequence $\looparrowright$

Problem Description

There is a sequence of integers. Your task is to find the longest subsequence that satisfies the following condition: the difference between the maximum element and the minimum element of the subsequence is no smaller than $m$ and no larger than $k$.

Input

There are multiple test cases.
For each test case, the first line has three integers, $n$, $m$ and $k$. $n$ is the length of the sequence and is in the range $[1,100000]$. $m$ and $k$ are in the range $[0,1000000]$. The second line has $n$ integers, which are all in the range $[0,1000000]$.
Proceed to the end of file.

Output

For each test case, print the length of the subsequence on a single line.

Sample Input

5 0 0
1 1 1 1 1
5 0 3
1 2 3 4 5

Sample Output

5
4

Translation

给一个序列，如果一个区间 $[l,r]$ 内的极差 $d$，满足 $m\le d\le k$，则认为这个区间是合法的，求合法区间的最大长度。

Idea

定义两个指针，即选定区间的左端点 $l$，右端点 $r$。考虑维护两个单调队列查询 $[l,r] $ 内的最值，从而获得极差。
我们可以先固定左端点 $l$，枚举右端点 $r$。如果 $[l,r]$ 内的极差大于 $k$，那么 $r$ 向右移动不可能减小极差，因此要将 $l$ 向右移动，令极差减小；这时候就涉及单调队列内队头的删除操作，如果 $l$ 向右移动时，单调队列的队头已经在 $l$ 外，那么就需要将队头删除，这一点与滑动窗口问题是类似的。如果 $[l,r]$ 内的极差小于 $m$，那么就不需要移动 $l $（移动 $l$ 只会让极差减小），让 $r$ 继续向右移动，就有可能增大极差，使极差大于等于 $m$ 。因此，只有区间极差大于 $k$ 时才可能触发删除队列队头的操作；如果区间极差小于 $m$，则需要另行判断。
每次 $r $ 向右移动一个单位，对单调队列进行操作之后就能确定左端点 $l$，如果确定的区间 $[l,r]$ 内的极差大于等于 $m $ ，那么就可以更新答案。
算法时间复杂度为 $O(n)$ 。

Code

#include<cstdio>
#include<algorithm>
#define N 100006 
using namespace std;
int a[N];
int n,m,k;
int ans;
int q_min[N],q_max[N];//单调队列
int head_min,tail_min;
int head_max,tail_max;
int main()
{
	//多组数据
	while(~scanf("%d%d%d",&n,&m,&k))
	{
		int i;
		ans=0;//初始化
		for(i=1;i<=n;i++) scanf("%d",a+i);
		if(m<=k)//特判，防止毒瘤数据。
		{
			int l,r;
			l=1;
			head_min=head_max=1;
			tail_min=tail_max=0;
			for(r=1;r<=n;r++)
			{
				//单调递增队列维护最小值
				while(head_min<=tail_min&&a[q_min[tail_min]]>=a[r]) tail_min--;
				q_min[++tail_min]=r;
				//单调递减队列维护最大值
				while(head_max<=tail_max&&a[q_max[tail_max]]<=a[r]) tail_max--;
				q_max[++tail_max]=r;
				/*
					若左边界向右移动时将单调队列队头覆盖
					相应地删除队头
				*/
				while(l<=r&&a[q_max[head_max]]-a[q_min[head_min]]>k)
				{
					if(l==q_min[head_min]) head_min++;
					if(l==q_max[head_max]) head_max++;
					l++;
				}
				if(a[q_max[head_max]]-a[q_min[head_min]]>=m) ans=max(r-l+1,ans);//满足条件则更新答案
			}
		}	
		printf("%d\n",ans);
	}
	return 0;
}

Postscript

这里的 $Subsequence$ 指数列的子列，非常坑。

2019牛客暑期多校训练营（第三场）F Planting Trees $\looparrowright$

题目描述

The semester is finally over and the summer holiday is coming. However, as part of your university’s graduation requirement, you have to take part in some social service during the holiday. Eventually, you decided to join a volunteer group which will plant trees in a mountain.
To simplify the problem, let’s represent the mountain where trees are to be planted with an $N \times N$ grid. Let’s number the rows $1$ to $N$ from top to bottom, and number the columns $1$ to $N$ from left to right. The elevation of the cell in the $i$-th row and $j$-th column is denoted by $a_{ij}$. Your leader decides that trees should be planted in a rectangular area within the mountain and that the maximum difference in elevation among the cells in that rectangle should not exceed M. In other words, if the coordinates of the top-left and the bottom-right corners of the rectangle are $(x_1,y_1)$ and $(x_2,y_2)$, then the condition $|a_{ij} - a_{kl}| \le M$ must hold for $x_1 \le i,$$k \le x_2,$$ \ y_1 $$\le $$j,l \le y_2$. Please help your leader calculate the maximum possible number of cells in such a rectangle so that he’ll know how many trees will be planted.

输入描述

The input contains multiple cases. The first line of the input contains a single integer $T$ $(1 \le T \le 1000)$, the number of cases.
For each case, the first line of the input contains two integers $N$ $(1 \le N \le 500)$ and $M (0 \le M \le 10^5)$. The following N lines each contain N integers, where the $j$-th integer in the $i$-th line denotes $a_{ij}$ $(1 \le a_{ij} \le 10^5)$.
It is guaranteed that the sum of $N^3$ over all cases does not exceed $2.5 \times 10^8$.

输出描述

For each case, print a single integer, the maximum number of cells in a valid rectangle.

示例1

输入
2
2 0
1 2
2 1
3 1
1 3 2
2 3 1
3 2 1
输出
1
4

翻译

给一个 $N\times N$ 的矩阵。如果一个子矩阵内的极差不大于 $M$，则认为这个子矩阵是合法的，输出合法子矩阵的最大面积。

分析

题目疯狂暗示对于所有的测试用例，$\sum N^3\le 2.5 \times 10^8$ ，所以要想一个时间复杂度为 $O(N^3)$ 的算法。
枚举子矩阵的上下边界,同时维护当前枚举的上下边界内每列的最值。这个时候可以将每一列的最值组成两个含有 $N$ 个数的序列，即 $maximum[i]$ 和 $minimum[i]$，将问题转化到一维；我们要找到一个满足条件：$\max\limits_{l\le i\le r} maximum[i]-\min\limits_{l\le i\le r} minimum[i]\le M$ 的最长区间 。将确定了上下边界后，枚举子矩阵的右边界 $r$。那么对于每一个 $r$，可以用一些数据结构或者二分法求解得到可行的最小左边界，那么总的时间复杂度为 $O(N^3\log N)$，显然会 $\text{TLE}$。实际上，可以考虑在枚举右边界的同时维护两个单调队列，两个单调队列分别区间维护最大值和最小值，每次访问队头就能得到一个区间内的极差。
设当前的最小左边界为$l$，如果区间 $[l,r]$ 内的极差大于 $M$，就将 $l$ 向右移动，如果单调队列中队头正好在左边界上，将队头一并删除。
算法的时间复杂度为 $O(N^3)$ 。

代码

#include<cstdio>
#include<algorithm>
#include<iostream>
#define inf 0x3f3f3f3f
#define N 506
using namespace std;
inline int read()//快读模板
{
	int X=0; bool flag=1; char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-') flag=0; ch=getchar();}
	while(ch>='0'&&ch<='9') {X=(X<<1)+(X<<3)+ch-'0'; ch=getchar();}
	if(flag) return X;
	return ~(X-1);
}
inline void write(int X)//快写模板
{
	if(X<0) {X=~(X-1); putchar('-');}
	if(X>9) write(X/10);
	putchar(X%10+'0');
}
int a[N][N];
int n,m;
/*--------单调队列相关---------*/
int q_max[N],q_min[N];//两个单调队列
int head_max,tail_max;
int head_min,tail_min;
int ans;
int maximum[N],minimum[N];//当前上下边界内每列的最值
int main()
{
	int _;
	for(cin>>_;_;_--)
	{
		ans=0;//初始化
		int i,j,k;
		int l,r;
		n=read();
		m=read();
		for(i=1;i<=n;i++)//读入
		{
			for(j=1;j<=n;j++)
			{
				a[i][j]=read();
			}
		}
		for(i=1;i<=n;i++)//枚举上边界
		{
			//初始化
			fill(minimum+1,minimum+n+1,inf);
			fill(maximum+1,maximum+n+1,-inf);
			for(j=i;j<=n;j++)//固定上边界，枚举下边界
			{
				int res=0;//res为合法区间[l,r]的最大长度
				for(k=1;k<=n;k++)//更新每列的最值
				{
					minimum[k]=min(minimum[k],a[j][k]);
					maximum[k]=max(maximum[k],a[j][k]);
				}
				//初始化队头和队尾
				head_max=head_min=1;
				tail_max=tail_min=0;
				l=1;//左边界初始值为1
				//to choose the more potential one
				for(r=1;r<=n;r++)//枚举右边界
				{
					/*-----------------维护两个单调队列-------------------*/
					//单调递增队列维护最小值
					while(head_max<=tail_max&&maximum[q_max[tail_max]]<=maximum[r]) tail_max--;
					q_max[++tail_max]=r;
					//单调递减队列维护最大值
					while(head_min<=tail_min&&minimum[q_min[tail_min]]>=minimum[r]) tail_min--;
					q_min[++tail_min]=r;
					while(l<=r&&maximum[q_max[head_max]]-minimum[q_min[head_min]]>m)//删除队头
					{
						/*
							若左边界向右移动时将单调队列队头覆盖
							相应地删除队头
						*/
						if(l==q_min[head_min]) head_min++;
						if(l==q_max[head_max]) head_max++;
						l++;//更新左边界
					}
					/*-------------------------------------------------*/
					res=max(res,r-l+1);//更新合法区间[l,r]的最大长度
				}
				ans=max(ans,(j-i+1)*res);//更新最大面积
			}
		}
		write(ans);
		putchar('\n');
	}
}

Postscript

时间卡得比较紧，用一下快读和快写。