单调栈、单调队列、RMQ

在做区间最值的时候，往往有些题目用单调栈会很简便，但是 $\text{RMQ}$ 也有它的使用方式，为节省题单数，就先放在一起。在完善这个题单的时候发现二分、前缀和、差分等一系列小技巧是需要长期使用的。 --- ### 首先放了一点模板题，请先行完成。 --- ### [奶牛排队](https://www.luogu.com.cn/problem/P6510) #### [$\text{RMQ +}$ 分治](https://www.luogu.com.cn/blog/syksykCCC/solution-p6510) 其实最适合大家的做法是这种（$\text{RMQ +}$ 分治），分治的思想是非常实用的好方法，这里提醒大家当有多个 $min$ 时应选取最右的 $min$，$max$ 应选取最左的 $max$。 #### [单调栈+暴力枚举](https://www.luogu.com.cn/blog/fusu2333/solution-p6510) 其实除了单调栈的预处理，整体思路非常像蓝书里 $\text{P225}$ 的一道例题 [与众不同](https://loj.ac/p/10121) ，而事实上题目也有些相似。 --- ### [选择客栈](https://www.luogu.com.cn/problem/P1311) 这道题用单调栈和 $\text{RMQ}$ 都可以做，大家可以练习一下。 --- ### [[USACO17DEC]Haybale Feast G](https://www.luogu.com.cn/problem/P4085) 中文题意在最下面，问题不是很大，但知道为什么题解里的方法都有点奇奇怪怪。在我眼里跟 [合唱队形](https://www.luogu.com.cn/problem/P1091) 非常像，同样是预处理+枚举C位， 本题是：单调栈+枚举最大值位置 预处理以我作为最大值时最左最右能到达什么位置， $L_i$ 表示最左能到达的位置，即离我最近的比我大的人是谁（$+1$）因为那个人不能取到。 同样的 $R_i$ 表示最右能到达的位置，即离我最近的比我大的人是谁（$-1$）因为那个人不能取到。 然后枚举 $i$，判断以 $i$ 作为最大值时，最大的 $F_{sum}$ 能不能满足条件，如果满足则进入对比，最终的得出最大值的最小值。 是一个普普通通的 $\text{O}(n)$做法。 --- ### [最近公共祖先 $\text{LCA}$](https://www.luogu.com.cn/problem/P3379) $\text{LCA}$ 有很多种求法，大家暂时会的只有欧拉序转 $\text{RMQ}$ 方法 [https://oi-wiki.org/graph/lca/](https://oi-wiki.org/graph/lca/)