0x12队列

队列是一种“先进先出”的线性数据结构。一般来讲，元素从右端进入队列（入队），从左端离开队列（出队）。于是我们称队列的左端为队头，右端为队尾。可以在 $C++$ 中用一个数组和两个变量（记录队头和队尾的位置）来实现队列结构。

元素进行多次入队、出队后，用于实现队列结构的数组的开头部分空间就会被严重浪费，所以我们经常将其优化为“循环队列”，也就是把队列看作一个首尾相接的环，只要队列中的元素个数在任意时刻都不超过环长，那么随着入队和出队操作的进行，存储元素的那一段位置就像沿着环不停地移动，重复利用着历史上曾被占用过的空间。C++ STL 中的 queue 就是一个循环队列，也是我们在代码中最常见的队列实现方式。

队列还有很多变体。例如两端都能插入或取出元素的双端队列（C++ STL deque），给每个元素附带一个评估值、出队时取出估值最大的、等价于一个二叉堆的优先队列（C++ STL priority_queue）。队列也是实现广度优先搜索的基本结构。对于队列的基本用法，读者应该已经比较熟悉，这里就不再赘述，而是把更多篇幅放在各种形式的队列的应用上。

【例题】Team Queue FOJ2259

有 $n$ 个小组要进行排队，每个小组中有若干个人。当一个人来到队伍时，如果队伍中已经有自己小组的成员，他就直接插队排在自己小组成员的后面，否则就站在队伍的最后面。给定不超过 $2 * 10^{5}$ 个入队指令（编号为 $X$ 的人来到队伍）和出队指令（队头的人出队），输出出队的顺序。

这是一道非常简单的题目，因为在任何时刻，同一个小组的人只要来到了队伍，就

会站在一起，所以我们建立一个队列 $Q_{0}$ 存储队伍中所有小组的编号，再为每个小组 $i$ 建立一个队列 $Q_{i}$ 存储队伍中这个小组的所有成员，一共 $n + 1$ 个队列。

当一个编号为 $X$ ，组号为 $Y$ 的人来到队伍时，我们直接把 $X$ 插入 $Q_{Y}$ 末尾。如果在插入之前 $Q_{Y}$ 是空的，则还要把 $Y$ 插入到 $Q_{0}$ 末尾，表明队伍最后出现了一个新的小组。

当接收到出队指令时，我们通过 $Q_{0}$ 得知排在最前面的小组组号 $Y$ ，然后再把 $Q_{Y}$ 的队头出队。出队后如果 $Q_{Y}$ 为空，就从 $Q_{0}$ 开头删除 $Y$ ，表明这个小组目前所有人已经离开。

*【例题】双端队列 BZOJ2457

Sherry 现在碰到了一个棘手的问题, 她需要对 $N \leq 2 * 10^{5}$ 个整数进行排序, 但是她手头能用的工具只有若干个双端队列。

她必须依次处理这 $N$ 个数，对于每个数 $A[i]$ ，Sherry 能做以下两件事之一：

1. 新建一个双端队列，并将 $A[i]$ 作为这个队列中的唯一的数。

2. 把 $A[i]$ 从已有队列的队头或队尾入队。

除此之外，对所有的数处理完成后，还要求这些队列能够按照一定的顺序连起来，得到一个非降的长度为 $N$ 的序列。请问Sherry最少需要多少个双端队列？

注：本题与数据结构关系不大，仅作为一道思考题，供读者训练思维。

这个问题很难直接求解，因为在不知道后面会有哪些数的情况下，我们作出的局部决策很可能造成某个数 $P$ 与 $Q$ 在同一个队列中，这样只要后面出现了介于 $P$ 和 $Q$ 之间的数，不管放到哪里都会导致无解（无法把队列连成一个有序序列）。这种情况启发我们，必须考虑按照数值的大小顺序而不是读入的顺序进行计算。

因为Sherry最后会把队列连成一个非降序列，所以我们不妨反过来思考，先把 $N$ 个数 $A[1 \sim N]$ 从小到大排序，然后分成尽量少的几段，让每一段对应原问题中一个合法的双端队列。

每一段需要满足什么条件才能对应原问题中的双端队列呢？我们可以依次取出排序后的所有数在原始数组 $A$ 中的下标，构成一个新的数组 $B$ 。

例如样例数据 $A = [360963]$ ，下标分别是[123456]。

排序后得到 $A' = [033669]$ ，对应原数组下标 $B = [316254]$ 。

经过分析可以发现，如果 $B$ 中的一段满足单谷性质（先单调递减，后单调递增），那么这一段就可以对应为原问题的双端队列（ $B$ 中保存的是下标，这一段的谷点就相当于第一个入队，递减的一段相当于从队头插入，递增的一段相当于从队尾插入）。

还需要注意的一点是，如果 $A$ 中存在几个相等的数，那么这几个数在排序时顺序是不定的，我们可以任意交换它们的顺序，使得 $B$ 数组能够分成更少的段数。

所以我们最终的算法是，按照 $A^{\prime}$ 中数值的异同，把 $B$ 看作若干个区间：

一个区间一个区间地对 $B$ 进行处理，最终拼成包含尽量少的段数的序列，其中每一段都具有单谷性质。我们可以用一个变量记录当前拼成的序列末尾处于递增状态还是递减状态，并用贪心策略尝试把当前区间递增或递减地接在序列末尾。以样例数据为例：

1.第一个区间始终看作递减区间插入序列，当前序列为[3]，正处于递减状态。
2. 第二个区间 [16]，因为 $6 > 3$ ，无法继续递减，只能以递增形式 [16] 插入序列，产生拐点，当前序列为 [316]，正处于递增状态。
3. 第三个区间 [25]，因为 $2 < 6$ ，无法继续递增，只能以递减形式 [52] 插入序列，产生拐点，单谷段数加 1。当前序列为 [31652]，正处于递减状态。
4. 第四个区间 [4], 因为 $4 > 2$ , 无法继续递减, 只能以递增形式 [4] 插入序列。

最终得到序列[316524]，包含[316],[524]两个单谷段，所以对应到原问题，需要2个双端队列。

单调队列

【例题】最大子序和 TYVJ1305

给定一个长度为 $N$ 的整数序列（可能有负数），从中找出一段长度不超过 $M$ 的连续子序列，使得子序列中所有数的和最大。 $N, M \leq 3 * 10^5$ 。

计算“区间和”的问题，一般转化为“两个前缀和相减”的形式进行求解。我们先求出 $S[i]$ 表示序列里前 $i$ 项的和，则连续子序列 $[L, R]$ 中数的和就等于 $S[R] - S[L - 1]$ 。所以原问题可以转化为：找出两个位置 $x, y$ ，使 $S[y] - S[x]$ 最大并且 $y - x \leq M$ 。

首先我们枚举右端点 $i$ ，当 $i$ 固定时，问题就变为：找到一个左端点 $j$ ，其中 $j \in [i - m, i - 1]$ 并且 $S[j]$ 最小。

不妨比较一下任意两个位置 $j$ 和 $k$ ，如果 $k < j < i$ 并且 $S[k] \geq S[j]$ ，那么对于所有大于等于 $i$ 的右端点， $k$ 永远不会成为最优选择。这是因为不但 $S[k]$ 不小于 $S[j]$ ，而且 $j$ 离 $i$ 更近，长度更不容易超过 $M$ ，即 $j$ 的生存能力比 $k$ 更强。所以当 $j$ 出现后， $k$ 就完全是一个无用的位置。

以上比较告诉我们，可能成为最优选择的策略集合一定是一个“下标位置递增、对应的前缀和 $S$ 的值也递增”的序列。我们可以用一个队列保存这个序列。随着右端点变从前向后扫描，我们对每个 $i$ 执行以下三个步骤：

1. 判断队头决策与 $i$ 的距离是否超出 $M$ 的范围，若超出则出队。

2. 此时队头就是右端点为 $i$ 时，左端点 $j$ 的最优选择。

3. 不断删除队尾决策，直到队尾对应的 $S$ 值小于 $S[i]$ 。然后把 $i$ 作为一个新的决策入队。

int  $l = 1$ $\mathbf{r} = 1$ $q[1] = 0$  // save choice  $j = 0$    
for(int i  $= 1$  ;i  $\Leftarrow$  n;  $\mathrm{i + + }$  ）  
{ while(1<=r&&q[l]<i-m)  $\mathbf{l} + +$  //step1) ans  $=$  max(ans,sum[i]-sum[q[l]]); //step2) while(1<=r&&sum[q[r]]>=sum[i])r--; //step3)  $\mathbf{q}[[+r]] = \mathbf{i};$  （20

这就是著名的单调队列算法，因为每个元素至多入队一次、出队一次，所以整个算法的时间复杂度为 $O(N)$ 。它的思想也是在决策集合（队列）中及时排除一定不是最优解的选择。单调队列是优化动态规划的一个重要手段，我们在第0x59节会详细讲解。