队列与栈()

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

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

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

单调栈

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

具体流程省略

P4147 玉蟾宫

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

这里再介绍一下悬线法

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

CF1601E Phys Ed Online

首先肯定是每个模 \(k\) 同余系都单独拎出来做
答案为 \(a_l+min(a_l,a_{l+1})+min(a_l,a_{l+1},a_{l+2})+\dots\)
设后面第一个比 \(i\) 小的位置为 \(nxt_i\),则答案为 \(\sum (nxt_i-i)a_i\)
那么就对单调栈上的这个东西做前缀和
具体询问的时候可以发现区间内只要最后一级的值会发生变化,即最小值的位置,这个可以手动算出,其它直接前缀和相减

  • 单调性相关题目中单调栈上做前缀和比较常见

单调队列

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

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

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

  • fence

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

  • cut the sequence

经过证明,可以发现最优候选 \(j\) 满足两个条件之一:

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

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

tricks

队列在动态最值中的应用

P2827 [NOIP2016 提高组] 蚯蚓

以这道题为例

P7078 [CSP-S2020] 贪吃蛇

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

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

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

B. 第二题

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

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

队列与栈的转化

棋盘

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

P1295 [TJOI2011]书架

\(dp\) 方程是 \(f_i=min (f_j+max[j+1,i])(\sum_{j+1}^i a\le m)\)
首先合法左端点是单调的,\(f\) 是单调的,\(max\) 是单调的
那么合法转移点一定是 \(a\) 单调的,且队列中 \(f_{q_j}+a_{q_{j+1}}\) 来更新答案
那么问题是需要快速求出单调队列的最小值
可以用栈来代替队列,每次取 \(mid\) 向左右构建单调栈

简要分析一下复杂度,从单调队列删除的总次数为 \(n\) 次,而每一次重构以后再删除 \(\frac{len}{2}\) 的长度才会重新重构,所以复杂度为 \(O(n)\)

双端队列可以用于 \(01\) \(bfs\),对于 \(0\) 边转移放在前面,\(1\) 边转移放在后面即可

————————

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

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

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

单调栈

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

具体流程省略

P4147 玉蟾宫

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

这里再介绍一下悬线法

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

CF1601E Phys Ed Online

首先肯定是每个模 \(k\) 同余系都单独拎出来做
答案为 \(a_l+min(a_l,a_{l+1})+min(a_l,a_{l+1},a_{l+2})+\dots\)
设后面第一个比 \(i\) 小的位置为 \(nxt_i\),则答案为 \(\sum (nxt_i-i)a_i\)
那么就对单调栈上的这个东西做前缀和
具体询问的时候可以发现区间内只要最后一级的值会发生变化,即最小值的位置,这个可以手动算出,其它直接前缀和相减

  • 单调性相关题目中单调栈上做前缀和比较常见

单调队列

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

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

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

  • fence

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

  • cut the sequence

经过证明,可以发现最优候选 \(j\) 满足两个条件之一:

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

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

tricks

队列在动态最值中的应用

P2827 [NOIP2016 提高组] 蚯蚓

以这道题为例

P7078 [CSP-S2020] 贪吃蛇

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

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

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

B. 第二题

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

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

队列与栈的转化

棋盘

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

P1295 [TJOI2011]书架

\(dp\) 方程是 \(f_i=min (f_j+max[j+1,i])(\sum_{j+1}^i a\le m)\)
首先合法左端点是单调的,\(f\) 是单调的,\(max\) 是单调的
那么合法转移点一定是 \(a\) 单调的,且队列中 \(f_{q_j}+a_{q_{j+1}}\) 来更新答案
那么问题是需要快速求出单调队列的最小值
可以用栈来代替队列,每次取 \(mid\) 向左右构建单调栈

简要分析一下复杂度,从单调队列删除的总次数为 \(n\) 次,而每一次重构以后再删除 \(\frac{len}{2}\) 的长度才会重新重构,所以复杂度为 \(O(n)\)

双端队列可以用于 \(01\) \(bfs\),对于 \(0\) 边转移放在前面,\(1\) 边转移放在后面即可