WARNING: 本文包含以下内容:

人外 (DS 确实不是人)

强暴 (某些确实挺暴力的)

高中生 (我自己就是)

基础内容#

实在太基础了拎出来单丢一节了

单调栈, 单调队列#

单次操作复杂度 , 均摊

多用于某些问题的优化, 这类问题多类似贪心, 可以排除一些无用解.

Hash#

多用于 计算某些难以 计算是否相等的数据.

字符串的最强算法 : SAM Hash

字符串的 Hash 可以简单的差分.

同样可以支持对树做 .

并查集#

维护集合的常用数据结构, 无法维护时考虑 LCT.

船新科技: 支持删除#

具体方法: 删除的时候新建一个空节点替代将被删除的节点即可. (惰性删除)

路径压缩的适用范围#

路径信息不重要的题目, 或者在压缩时可以快速并且不破坏的维护路径上的信息.

启发式合并与按秩合并#

启发式合并: 考察即将合并的两个集合的大小, 永远将小的集合合并到大的上 (如果能在 内完成合并, 即可实现 时间复杂度的合并.)

按秩合并: 仅在并查集上能完成 时间复杂度. 按照深度, 将深度小的合并到深度大的上, 多用于路径压缩无法使用的场景. (例如可持久化并查集)

堆#

支持插入删除的维护最大值. 某些支持一些额外操作.

左偏树 (可并堆)#

定义某个节点的 是其到最近叶子的距离, 左偏树在满足堆性质的基础上满足自己的 为右儿子的 值增加 (即左儿子的 不大于右儿子的 ). 左偏树的左链的长度是 , 的.

考虑解决两个左偏树的合并:

int dist[_], val[_], tr[_][2];
int merge(int x, int y) {
  if(!x||!y) return x+y;
  if(val[x] >= val[y]) swap(x, y);
  tr[x][1]=merge(tr[x][1], y);
  if(dist[tr[x][0]] <= dist[tr[x][1]]) swap(tr[x][0], tr[x][1]);
  dist[x]=dist[tr[x][1]]+1;
  return x;
}

考虑使用此操作支持其他操作:

int newHeap(int val) : 直接支持即可,

void insert(int x, int val) : merge(x, newHeap(val)); 即可,

void del(int x) : merge(tr[x][0], tr[x][1]) 后从下向上考虑, 每当 性质被破坏时, 暴力维护即可, .

对堆中的所有对象全体操作类: 凡是不改变相对大小(加减乘正数), 或者做 次操作只改变 次, 并且这种改变与当前堆中的数无关 (例如乘负数, 乘 (复数按照模长比较).).

「SCOI2011」棘手的操作#

题面#

有 个节点, 标号从 到 , 这 个节点一开始相互不连通. 第 个节点的初始权值为, 接下来有如下一些操作:

• U x y 加一条边, 连接第 个节点和第 个节点.
• A1 x v 将第 个节点的权值增加 .
• A2 x v 将第 个节点所在的连通块的所有节点的权值都增加 .
• A3 v 将所有节点的权值都增加
• F1 x 输出第 个节点当前的权值。
• F2 x 输出第 个节点所在的连通块中, 权值最大的节点的权值.
• F3 输出所有节点中, 权值最大的节点的权值.

解法#

考虑到操作 F2, 显然应该使用可并堆.

考虑到除了 A2 操作, 其他操作都是基本可并堆操作. 这里只讨论 A2 操作. 不妨考虑对于每个堆, 在堆顶维护一个 表示这个堆的总体增量. 在合并时, 保留大小较大堆顶的 , 暴力修改大小较小堆顶的 tag.

ODT#

维护序列信息, 基于随机性. 要求操作中有区间推平.

具体来讲, 维护一个区间的集合. 在一个区间被推平时, 我们将其所有位置拆出来, 然后新建一个新区间维护这些位置的信息.

采用 std::set 维护这些区间.

进阶 (?) 内容#

树状数组#

单点修改, 前缀和.

对于任意一个序列 , 我们不妨考虑这样的一个 , 其中 . 考虑 构成的树状结构, 即对于数上的节点 , 权值为 , 父亲为 .容易证明 . 因此查询 时, 考虑每次将 计入答案, 然后令 . 这样能够覆盖 的所有节点. 修改时, 每次更新 , 然后令 .

常用 trick : 倍增砍老哥 ()

线段树#

万恶之源.

区间修改, 区间求和.

对于 , 定义 为最大的 满足 .