原始线性信息
- 原始版本支持线性信息的动态单点修改、动态单点查询
- 维护差分数组及其前缀和可实现静态区间修改、查询
链表
链表实现
- 数组实现：val[i] 记录值，nex[i] 指向下一元素
- 伪删除：墓碑 tomb[i]
链表应用
- 数列 $O(1)$ 单点增删，$O(n)$ 单点改查
- 快慢指针判断是否成环以及寻找中间节点
栈
栈应用
后进先出特性的问题：$O(1)$ 栈顶增删改查
- 处理算术表达式
- 前/后缀表达式生成：初始化两个栈，从右向左/左向右扫描表达式，遇数压数栈，遇运算符比较其与符号栈顶优先级
- 若栈空或栈顶为’(‘/’)‘，则压栈；若栈顶优先级高，则压栈，否则出栈直至可以入栈。’(‘/’)‘优先级最低，直接入栈，遇’)‘/’(‘出栈直至’(‘/’)’出栈
- 前/后缀表达式求值：从右向左/左向右扫描表达式，遇数字压栈，遇运算符弹栈顶两数计算后压栈
- 前/后缀表达式生成：初始化两个栈，从右向左/左向右扫描表达式，遇数压数栈，遇运算符比较其与符号栈顶优先级
- 处理括号匹配
- 左括号入栈，遇右括号出栈，若遇右括号栈空或最后栈不空，则不匹配
- 实现 DFS、函数栈、可撤销并查集
- 结合 KMP/AC自动机实现删除模式串
队列
队列应用
先进后出特性的问题：$O(1)$ 首尾增删改查
- 实现 BFS
- 消息队列
哈希表
实现
将大范围稀疏数据映射到小范围键值
应用
键值对存储数据
偏序单调信息
基于具有反对称性、传递性的偏序关系建立的数据结构，维护偏序关系的单调性规律。
堆
堆实现
- 堆是一棵每个节点的键值都与其父亲满足单调性的满二叉树
- 查询：根节点即最值 $O(1)$
- 插入：末尾添加，向上/下调整 $O(\log n)$
- 删除：向上/下调整 $O(\log n)$
- 修改：向上/下调整 $O(\log n)$
- priority_queue 默认大顶堆
堆应用
#include <queue>
#include <utility>
void solve(){
priority_queue<pair<int,int>> h;//pair排序优先级：先first后second，默认大顶堆，即都按从大到小顺序排序
h.push(make_pair(v[i], i));//都按从大到小顺序排序
h.push(make_pair(-v[i], i));//加负号颠倒大小的 first 按从小到大顺序，second按从大到小顺序
}
堆排序
$O(n\log n)$
后悔贪心
TopK问题
单次操作 $O(\log K)$
动态维护序列第k大（动态k值）
单次操作 $O(\log K)$
- 小根堆维护前k大值，大根堆维护剩余
- 维护操作：在大小根堆间转移元素保证小根堆维护前k大值
- 插入元素，查询/删除小根堆顶（第k大元素）
单调栈
单调栈实现
- 维护栈内元素单调性的前提下弹出最少元素
- 记录元素序号，栈内元素满足保序性
- 栈内元素满足单调性，栈顶为最值
单调栈应用
结束标识符用于强制遗留元素出栈以避免栈内遗留元素的贡献未计算。
查询每个数两侧首个大/小于该数的元素序号
$O(n)$ 即对 $a_i$ 求出满足 $i<j\land a_i<a_j \land \forall k \in (i,j)\lnot a_i<a_k$ 法一：
- 逆序遍历获取每个数后首个大/小于于该数的元素，栈顶为 $a_j$ ，该点为 $a_i$
- 对每个点：弹出栈顶不比该点大/小的元素，剩下的栈顶元素即为首个大/小于该数的元素
sc int stk[N], ans[N];
int top=0;
a[0]=1e9+5;
for(int i=n; i>=1; --i){
while(top && a[stk[top]]<=a[i]) --top;
ans[i]=(top ? stk[top] : 0);
stk[++top]=i;
}
while(top && a[stk[top]]<=a[0]) --top;//处理栈内遗留元素
法二：
- 正序遍历获取每个数后首个大/小于该数的元素，栈内为 $a_i$ ，该点为 $a_j$
- 对每个点：弹出栈顶比其小/大的元素，该点即为弹出元素后侧首个大于/小于弹出元素的数
sc int stk[N], ans[N];
int top=0;
a[n+1]=1e9+5;
for(int i=1; i<=n; ++i){
while(top && a[stk[top]]<a[i]) ans[stk[top--]]=i;
stk[++top]=i;
}
while(top && a[stk[top]]<a[n+1]) ans[stk[top--]]=0;//处理栈内遗留元素
离线RMQ
$O(q\log q+q\log n)$
- 所有询问按右端点排序，每次在序列上从左到右扫描到当前询问的右端点处，将扫描到的元素插入单调栈
- 每次回答询问时，单调栈中元素位置 $\leq r$ 且满足单调性，二分查找单调栈上首个 $\geq l$ 的元素即答案
单调队列
单调队列实现
- 支持队尾插入和双端删除，维护单调性前提下队尾删除最少元素
- 查询：队列内元素满足单调性，队首即最值
- 记录元素序号，队列内元素满足保序性
单调队列应用
维护滑动窗口内静态最值
$O(n)$
sc int q[N];
auto&& getMin=[&]()->void{
int head=0, tail=-1;//初始化队首队尾
for(int i=1; i<kk; ++i){//初始化滑动窗口
while(head<=tail && a[q[tail]]>=a[i]) --tail;/*队尾插入并通过删除维护单调性*/
q[++tail]=i;
}
for(int i=kk; i<=n; ++i){//窗口滑动
while(head<=tail && a[q[tail]]>=a[i]) --tail;/*队尾插入并通过删除维护单调性*/
q[++tail]=i;
while(q[head]<=i-kk) ++head;/*弹出队首保证滑动窗口大小为 kk*/
cout<<a[q[head]]<<" ";//输出长度为kk的窗口的最小值
}
};
