队列

队列是一种先进先出（FIFO)的线性表。 它在很多地方都能够用到，例如： 当多个任务分配给打印机时，为了防止冲突，创建一个队列，把任务入队，按先入先出的原则处理任务。 当多个用户要访问远程服务端的文件时，也用到队列，满足先来先服务的原则。 ……等等

不多说，写这篇博文的目的是记录复习之路的日常，在算法之中，队列也经常用于BFS（宽度优先搜索）之中，但在这方面过于简单，不赘述。

单调性

在这里主要讲的是其单调性的应用，在某些竞赛题目中属于大杀器的范围。 个人觉得江苏2008年的省选题还不错：洛谷1198 最大数

其他的不说，直接说思路。 思路：题目中描述道：查询当前数列中末尾L个数中的最大的数，并输出这个数的值。这个是Q操作，而A操作是将n加上t，其中t是最近一次查询操作的答案（如果还未执行过查询操作，则t=0)，并将所得结果对一个固定的常数D取模，将所得答案插入到数列的末尾。由这两句话我们能想到单调队列，我们可以只记录‘可能’是答案的值，也就是说，我们可以维护一个从队首到队尾单调递减的队列（s[],此队列仅保存数据位置，即某个数在数组a中的位置）。 假如向队尾插入一个已经计算好了的数a[i]，我们将此数据插入到符合条件a[s[j]] > a[i] ，并将此a[i]的数据编号插入到s[j]的后一个位置，即s[j+1] = i。那么便做好了插入工作。 再来说一下查询操作，我们可以很容易地知道s[]是一个a数组位置的递增队列，所以就可以直接用STL中的lower_bound()函数在区间[a.size - L + 1，a.size]中进行二分查找，查找s中第一个s[pos] <= a.size - L + 1的第一个数，就是区间[a.size - L + 1，a.size]中最大数的位置编号，最后将其赋值给t输出便可。 代码如下：

#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> using namespace std; const int MAXN = 200000 + 10; int a[MAXN],s[MAXN]; int main(){ char c[3]; int M,D,x,top = 0,t = 0,len = 0; scanf("%d%d",&M,&D); while(M--){ scanf("%s %d",c,&x); if(c[0] == 'A'){ x = (x + t) % D; a[++len] = x; while(top > 0 && a[s[top]] <= x)top--; s[++top] = len; } else printf("%d\n",t = a[s[lower_bound(s+1,s+top+1,len - x + 1) - s]]); //在单调队列中二分查找位置比x小的后一个位置 } return 0; }

队列复习大概就是到这里了，今天心情算不太好…. 特别不高兴…… ！！… RP++