单调队列优化 DP
前置知识：单调队列
一，概览
某些特定
DP，其当前状态的所有值都可以通过上一状态的某个连续段得到，要对这个连续段求区间最值，相邻状态的区间上下界单调变化。
对于这类动态规划问题，发现我们可以在状态转移当中引入单调队列，对 DP
进行优化。
二，思路
例题：最大子序和
给定一个长度为 \(N\)
的整数序列，从中找出一段长度不超过 \(M\)
的连续子序列，使得子序列中所有数的和最大。\(N,M\leq 3\times 10^5\)。
对于这道题，其答案可以形式化表示为：
\(ans=\) \(max_{1\leq i\leq N}\) \((sum[i]-\) \(min_{i-M\leq j\leq i-1}\) \(sum[j])\)
其中，\(i\)
类似于动态规划中的状态，\(j\)
类似于动态规划中的决策。我们从小到大枚举每个 \(i\in[1,N]\) 时，当 \(i\) 增大 \(1\) 时，\(j\) 的取值范围 \([i-M,i-1]\) 的上下界也同时增大 \(1\)，变为 \([i-M+1...
单调队列
一，概览
单调队列的重点在于单调和队列
单调反映了元素变化的规律是递增或递减；
队列意味着对元素的操作只能在队头和队尾进行。
二，实现
建立一个队列，考虑要向里插入一个元素：
比较要插入的元素和现有的队尾，若满足所需的单调性，则直接插入队尾，若不满足单调性，则重复弹出队尾直到满足单调性或队列为空，之后将新元素插入队尾。
单调队列最经典的实现就是滑动窗口，即给出一个数组 \(a_{1,2,...,n}\)，给出一个长度 \(k\)，在数组中找到每一段长为 \(k\) 的区间的区间最值。
模板题面
Luogu P1886
滑动窗口/【模板】单调队列
有一个长为 \(n\) 的序列 \(a\)，以及一个大小为 \(k\)
的窗口。现在这个从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最大值和最小值。
输入一共有两行，第一行有两个正整数 \(n,k\)。 第二行 \(n\) 个整数，表示序列 \(a\)
输出共两行，第一行为每次窗口滑动的最小值
第二行为每次窗口滑动的最大值
样例输入 #1
128 ...
左偏树
左偏树是可并堆的一种，具有堆的性质，可快速合并.
维护如下信息：\(\text{val}\)：权值，\(\text{ls}\)：左儿子，\(\text{rs}\)：右儿子，\(\text{dist}\)：距离，\(\text{fa}\)：父亲。
一，dist
对于一棵二叉树，我们定义外结点为左儿子或右儿子为空的结点。
定义一个外结点的 \(\text{dist}\) 为
\(1\)，非外结点的 \(\text{dist}\)
为其到子树中最近外结点的距离加一，空结点的 \(\text{dist}\) 为 \(0\)。
现在有一棵 \(n\)
个结点的二叉树，则有如下性质：
根的 \(\text{dist}\) 不超过
\([log(n+1)]\)；
若该二叉树根的 \(\text{dist}\)
为 \(x\)，则至少有 \(x-1\) 层为满二叉树，至少有 \(2^x-1\) 个结点。
二，左偏树的性质
左偏树是一棵二叉树，它具有如下性质：
堆的性质；
每个结点左儿子的 \(\text{dist}\)
大于等于右儿子的 \...
AC 自动机
AC 自动机是以 Trie 树结构为基础，结合 KMP
思想建立的自动机，用于解决多模式匹配等任务。
一，概览
用两步建立一个 AC 自动机：
建立 Trie 树。（以 Trie 树为基础）
对 Trie 树上的所有结点构造失配指针。（结合 KMP 思想）
之后便可以用它进行匹配了。
二，字典树构建
AC 自动机所用的 Trie 就是普通的 Trie。
在 Trie 当中，结点表示某个模式串的前缀。Trie
的结点表示状态，边表示转移。
对于若干模式串 \(s_1,s_2,...,s_n\)，将它们构建成字典树后所有状态的集合记为
\(Q\)。
123456789101112int cnt,tr[1000005][26],ended[1000005];void insert(string s){ int u=0; for(int i=0;s[i];i++) { if(!tr[u][s[i]-'a']) tr[u][s[i]-'a...
自动机
自动机是一种对信号序列进行判定的数学模型
一，主观理解
以上为自动机的定义，该定义十分抽象，以下为笔者的主观理解。
1. 自动机建立的基础
即定义中的“信号序列”。
我们可以把这个所谓“信号序列”理解为一个串，串的每一位上存有信息。
eg.
字符串是一个“信号序列”，数组是一个“信号序列”，一个数的各位可以构成一个“信号序列”。
自动机便是建立在信号序列的基础上的。
2. 自动机要干什么
即定义中的“判定”。
对针对信号序列的特定命题给出真或假的回答。
eg.
判断一个数是奇数还是偶数是判定，判断一个字符串是否回文是判定，判断一个字符串是否是一特定字符串的子串是判定。
3. 自动机的具象化理解
虽然自动机是一个抽象的数学模型，但在 OI
里，自动机常可以被理解为一张有向图，我们把自动机所求的判定拆解为若干小判定，每一个结点都代表某次判定时的状态，结点向结点转移便是判定的过程，判定会有多种结果，因而一个结点的不同子结点便代表判定的不同结果。
以下图片有助于更好地理解：
eg. 在 Trie 树上查找某字符串是...