双指针法
利用单调性优化暴力中最简单的一种方法：按某种顺序枚举问题的一种条件，满足枚举条件的最优解以某种固定的方式变化。
P1102 A-B 数对
排序后从小到大枚举左端点 \(B\)，右端点 \(A\) 单调不降，每次向右找到其对应的一段区间即可。
P1638 逛画展
从左往右枚举左端点，每次移动时原左端点那幅画对应的画家在区间中可能没有作品了，此时必须向右移动右端点直至该画家的某一幅画。
P1115 最大子段和
枚举右端点，最优左端点可以做到单调不降，否则先前将向左移动的这部分选入和会更大。
其实就是找前缀和最小的左端点。
空间换时间
顾名思义，当题目空间限制没用完时尽量用它去优化时间总是没问题的。
P7072 「CSPJ2020」直播获奖
直观想法是每次加入一个成绩就排序，显然会超时。
注意到成绩范围很小，会存在大量重复，所以额外用桶记录每种成绩出现的次数即可较快找到分数线。
这其实就是计数排序。
P2671 「NOIP2015」求和
最裸暴力即三重循环枚举 \(x,y,z\)。
注意到 \(y=\frac{z-x}{2}\)，所以只需要统计 \(z-x\) 为偶数的情况，并且 \(y\) 对分数计算无影响。
拆式子，从小到大枚举 \(z\)，每种颜色都记录两种奇偶性的 \(x\) 的前缀信息即可。
如果放到全局来计算则只需要记录数量和数字和两种信息，节省了一半的空间。
P4147 玉蟾宫
简单介绍一下悬线法。单调栈求解其实也是悬线法，只是过程是一次性的不太形象。
悬线就是从障碍格向下的若干个连续非障碍格，显然每个非障碍格对应唯一悬线末端。
先预处理出每个非障碍格向左向右遇到的第一个障碍格位置，进而处理出每条悬线向左向右能拓展到的最远位置。
最大面积的矩阵的高一定可以对应到一条悬线，否则这个矩阵可以向上拓展变得更高。
单调栈 & 单调队列
单调栈即满足单调性的栈结构，单调队列即满足单调性的队列结构。
这决定了它们的用途。单调栈由于只能在栈顶操作，只能解决下标或其对应信息没有限制的问题，而单调队列则没有这个顾虑。
有两类问题，一类是求下标有限制的区间内最优解，自然用单调队列；另一类是求某一侧第一个更优的位置，自然用单调栈，但这仅仅是单调队列中弹出队尾的那一部分而已。
就比如说求某一侧下标有限制的第一个更优的位置，它也是用单调队列，只不过不常见而已。
单调队列的本质是贪心。
P2866 「USACO06NOV」Bad Hair Day S
不好直接求每头牛能看见几头牛，考虑求每头牛能被几头牛看见。
维护单调递减的单调栈，这样栈中的牛均能看见新进来的牛，不在栈中的牛说明后面有高于它的，肯定看不见。
P1950 长方形
对于一个矩形，我们在它的右下角处将其计入答案。
枚举行，从左往右维护单调不降的单调栈。当栈顶高度大于当前高度时，高出的那部分就不能作为矩形的左上角了，所以应该将其推平。
当然我们并不是直接模拟推平操作，将相同高度合并，额外记录左端点即可。
P2032 扫描
模板。
P2216 理想的正方形
先在行中用单调队列将最值推到矩形最右侧那一列，再在列中用单调队列将最值推到矩形右下角。
作业与例题一同放在团队作业中，再简单也请实现一遍，反正写写也快。
本次内容较为简单，多余时间可以补一下之前 myh 作业中相关部分。
标签：技巧,队列,第一章,枚举,端点,悬线,矩形,优化,单调 From： https://www.cnblogs.com/landsol/p/17128804.html