STL

  • vector 的 size 是 unsigned 的，-1 会爆炸。

二叉堆

查询是 O(1）的。

加点你直接在末尾加然后一路交换父亲和自己。

删点你就把最后的点加到头上然一路顺着儿子找下去，把最小的儿子放上来。

合并果子的证明

类似于一棵二叉树，最优方案 $\sum_{i}a_idep_i$。

  • 最小的两堆一定最深。不然交换最深层的某堆更优。

  • 同层的叶子互换无影响。

然后归纳。

经典问题

给出正数序列求前 k 小的子区间和。

从堆里挑出一个区间，然后把它的左右两边的扩展加入堆。

并查集

bzoj2054

区间赋值，一次询问。

经典时间倒流，每个位置只会被修改一次。

LCA

BJOI2014 大融合

支持加边，查经过某条边的简单路径数量。

先离线建树，然后并查集动态维护子树大小，这个可以变成链加，单点查，树状数组dfn维护即可。

P4211

q 次求 $\sum_{l\le i\le r}dep(lca(i,z))$

经典结论：深度=点到根之间所有点的数量。

因此我们差分，每次把一个点到根的路径 +1，然后查询 z 到 根的路径。

P4216

求第 i-c 时刻 x->y 的和，树上差分+树状数组维护。

ST 表

经典问题

给出一棵 n 个点的树，以及一个长为 n 的序列 a ， a[i] 表示 a 序
列 i 位置为一个树上编号为 a[i] 的节点，树的边权为 1

有 m 次询问，每次询问给两个 a 的区间，求从两个区间中各选出
一个点能得到的树上最远距离。

就是从 $[l1,r1]$ 中选一个 i ， $[l2,r2]$ 中选一个 j ，求 $max{dist(a[i],a[j])}$

m 很大。

然

这题很典，就是你发现 $A\cup B$ 构成的直径就是 $A$ 中选一个直径，$B$ 中选一个直径，四个点匹配一下。

直接用 ST 表维护直径的端点，可以做到 $O(n\log n)-O(1)$

也就是 ST 表支持可合并信息的不带修，O(1) 查询。

01trie

bzoj4212

求有多少模式串的前缀是 s1，后缀是 s2。

转化为两个 trie 的 dfn。然后二维数点。

不可重复？

考虑挂在一棵 trie 上，后缀用哈希存下来，问题变成查询一个子树当中的哈希值等于一个值的数量。

以哈希为第一关键字，dfn为第二关键字排序，直接二分查就好。

TEST_68

n 个点的树，点有点权，对于每个 x，其答案为其所在的子树外的所有点中，选两个可以相同的点 i,j， ai xor aj 的最大值，如果选不出两个点，认为 x 的答案为 0。

绷不住了，常见套路。

你注意到除了 x,y 到根的路径并以外，其他所有点的权值都是满足 ax xor ay 最大的 x,y。

然后你只剩下两条链需要维护了，直接对着 dfn 序暴力维护就赢了。

P6072

找两条点不相交的路径，满足边的异或和的和最大。

首先拆成点到根的权值异或，然后又有结论：树上两条路径点不相交，则一定存在一个点 i，使得一条路径落在 i 的子树里，另一条路径落在 i 的子树外。

子树外选点参见上一个题，子树内选点可以 nlog^2 n 做启发式合并。

考虑找到全局最大的 x,y，显然 lca(x,y) 的祖先答案就是 x,y。

当 x,y 都在子树外的时候，这个点一定落在 x->y 路径的毛毛虫上是最优的，暴力插入复杂度是正确的 O(nlog)，因为点不相交。

当 x 在子树内 y 在子树外的时候，你发现插入总次数也是 O(n)，所以能做。

哈希

维护某种信息快速判断两个集合是否相等。

随机化算法。

P5310

给出 A,B 长度为 n,m

Q 次操作，每次修改 B 的一个位置，查询 A 有多少长度为 m 的子串和 B 完全匹配。

哈希，然后变成查询有多少个数和 B 相等。

unordered map 做到 O(n)。

UOJ207 弱化版

给定一棵 n 个点的树，以及一个初始为空的集合，集合里的数据类型为二元组，有 m 次操作，每次操作可能是在集合中插入一个二元组 (x,y) ，删除一个二元组
，或者查询树上一条边，是否满足对所有集合中的二元组
(a,b) ， a 到 b 的简单路径都经过了这条边，即假设删掉这条边，是否会将集合中所有二元组都分到了两个部分。

对于每个点对随机一个权值，然后查询子树的异或和。

线段树&平衡树

bzoj4373

询问 [l,r] 能否形成一个公差为 k 的等差数列。

支持动态修改一个位置的值。

你 hash 可以做。

考虑确定性算法，公差为 k 的等差数列中任意选出两个元素，做差一定是 k 的倍数。

所以我们原序列做差分之后 gcd 一定等于 k

可以证明，差分后 gcd 等于 k 并且序列中没有重复元素并且最大值减最小值是合法的，是它为等差数列的充要条件。

P3586

单点修改，查询每次选出 c 个正数减去 1，这种操作是否能进行 s 次。

对于每次询问：

$a_i\ge s$ 则 $a_i$ 可以每次 s 都选中，不然只能选 ai 次，考虑大于等于 $s$ 的数个数有 $k$，小于 $s$ 的和为 sum，则 $sum\ge (c-k)s$ 是充要的。

用平衡树维护。

P6105

维护一个集合 S，支持插入 x，删除 x，询问从 S 中选出两个不同的元素，其和 mod C 最大，C 是固定的。强制在线。

只需要考虑 $x+y<C$ 的情况。

目前非平凡的部分在于从 $[0,\frac C2)$ 中选一个 $x$，从 $[\frac C2,C)$ 中选一个 $y$，$x+y<C$，也就是 $x<C-y$。

也就是我们要最小化 $(C-y)-x$。

用平衡树维护子树当中最小的 $C-y$，最大的 $x$，最小的 $C-y-x$，然后做了。

问题等价于我们从 $A$ 中掏出来一个 $x$，从 $B$ 中掏出来一个 $y$，使得 $x<y$ 并且 $y-x$ 尽可能小。

其实就是让 $x$ 是 $y$ 的一个前驱。

这个东西可以直接平衡树维护，非常强大。

更强大的是，你发现你可以对于每个 $A$ 中的 $x$，维护出其在 $B$ 中的后缀 $C-y$，对于每个 $B$ 集合中的 $C-y$，维护出它在 $A$ 中的前驱 $x$。

每次修改前驱后继变化是 $O(1)$ 的。

于是直接就做完了。

P6617

单点修改，查询区间是否存在两个数和为 $w$。

首先二维数点转化，每个点 $x$，前驱最近的 $w-x$，这个和区间颜色数的转化类似。

接下来考虑带修改。

你发现一次修改会影响 $O(n)$ 个位置，寄了。

考虑减少修改的数量。

你发现包含关系的时候，只需要选最短的那个。

因此每个点只有最短的匹配是有用的。

所以我们对于每个位置，

P5069

如果一个位置被操作了，那么相邻两个位置显然没有贡献了。

又发现对于一个极长的单调区间，一定是奇数位置或者偶数位置的和。

树套树

单点修改，矩形查询。