队列与栈（待补订）

栈

栈的最基本用途可能就是表达式求值了

P1310 [NOIP2011 普及组] 表达式的值

大概捋一下转化过程
如果是左括号或乘号，直接入栈
如果是右括号，一直弹栈知道出来左括号
如果是加号，则先弹栈直到没有乘号
乘号就直接放

单调栈

单调栈是一种快速求解序列中每个位置左右第一个大于/小于自己值的位置的算法，在大部分情况下可以很好地代替笛卡尔树

具体流程省略

---

直方图中最大的矩形

模板题

---

P4147 玉蟾宫

把一维变成二维了而已，预处理每行上方最长连续高度即可，然后再跑最大矩形

这里再介绍一下悬线法

首先预处理 \(up[i][j]\) 表示向上最大高度，即悬着的“线”
那么对于每条线只要知道左右最远能移动到的位置即可
\(l[i][j]\) 和 \(r[i][j]\) 就是这个左右
如果上一行这一列不是障碍，那么 \(l,r\) 分别取 \(min\)，否则意味着开启一块新的矩形

---

单调队列

单调队列可以用于优化如下类型的 \(dp\) 转移：

\[f_i=max_{l_i\le j\le r_i}\{f_j+val(i,j)\} \]

要求 \(l_ir\) 和 \(r_i\) 单调，且 \(val(i,j)\) 之和 \(i\) 与 \(j\) 中的一个有关（指没有乘积项）

---

下面的例子直接写出 \(dp\) 方程来进行优化

• fence

\[f[i][j]=max_{j-l_i\le k\le S_i-1}{f[i-1][k]+P_i(j-k)} \]

发现 \(val\) 部分只与 \(k\) 有关，而当 \(j\) 变大 \(1\) 的时候，候选 \(k\) 集合也是单调的，那么用单调队列维护即可

---

• cut the sequence

\[f[i]=min_{0\le j

经过证明，可以发现最有候选 \(j\) 满足两个条件之一：

1. \(j\) 是满足和条件的最小的
2. \(j\) 比 \([j+1,i]\) 的值都大

那么可以维护一个单调递减的队列，存放所有合法的 \(j\)
但是注意这时 \(a_j\) 最大不能代表最优转移，而是将 \(f[j]+max{a_k}\) 都放入堆中，动态查询出一个最大的转移

---

tricks

队列在动态最值中的应用

P2827 [NOIP2016 提高组] 蚯蚓

以这道题为例

---

P7078 [CSP-S2020] 贪吃蛇

毕竟蛇与蚯蚓是类似的生物，这道题中也用到了类似的思想，详见

---

P6033 [NOIP2004 提高组] 合并果子 加强版

构建哈夫曼树的时候同样可以用这种方式代替过慢的堆

---

B. 第二题

甚至跑最长路都可以用这种技巧优化

---

总之用到堆并且时间挺卡的题都想想这个吧~

队列与栈的转化

棋盘

矩乘啥的都先不说了
可以发现维护出的前缀积当队首出队时贡献是不能刨去的，因为不满足交换律
那么维护两个栈，每次有插入操作直接插在第二个栈后面，有删除操作，能弹第一个就弹第一个，否则把第二个栈中所有元素拿出来放进第一个，顺便处理前缀积
这样很好地做到了矩乘顺序的倒序，而每个元素出栈一次，复杂度也得到了保证