启发式合并

· · 算法·理论

如题，这是一篇关于启发式合并的文章。

前情提要

什么是启发式合并？这源于一种十分暴力的想法。举个十分简单的例子，比如说，现在一共有 n 个集合，你现在要将这 n 个集合合并成一个大集合，每次合并只能遍历一个集合，将这个集合所有的元素取出来，放入另一个集合中。

如果取出和放入操作都是 O(1) 的话，朴素的实现这个过程当然是 O(n^2) 的。

但很显然，我们会有一种直接的想法，就是当合并两个集合时，将小集合合并到大集合里，这样可以减少一点时间复杂度，那具体时间复杂度是什么呢，其实是 O(n \log n) 的，下面我们来证明一下。

对于启发式合并，证明是相似的，我们可以考虑一个点会被合并多少次。我们每次将小集合合并到大集合中，每次操作集合大小至少增加一倍，所以每个元素至多被取出和放入 \log n 次，总时间复杂度 O(n \log n)（注意是将小集合合并到大集合，所以说大集合的元素不需要取出，只需要将小集合的元素放入大集合中，所以说这么证明是正确的）。

现在你应该了解了什么是启发式合并，现在我们来练习一下。

序列上启发式合并

P3201 [HNOI2009] 梦幻布丁

题目大意：n 个布丁，每个布丁都有颜色。给定 m 次操作，每次操作，可以将一种颜色的布丁全部变成另一种颜色；或者询问当前一共有多少颜色段。

题解：首先，令 cnt 表示相邻布丁颜色相同的个数，则可以将一共有多少颜色段转化成 n - cnt，所以我们只需要对于每一次操作维护 cnt 的变化即可。

然后，我们可以思考什么时候改变布丁的颜色会使答案发生改变，假如说我们将颜色 x 变成颜色 y，答案发生改变当且仅当颜色 x 与颜色 y 是相邻的。所以说，实际上，将颜色 x 变为颜色 y 与将颜色 y 变为颜色 x 所对答案产生的变化是相同的。

我们不妨考虑按照启发式合并的思路，如果我们每次能让同种颜色数量少的合并到同种颜色数量多的，尽管我们暴力的去合并，时间复杂度也是 O(n \log n) 的。

那么对于每次操作，如果要将颜色 x 的布丁全部变成颜色 y，不妨比较 size_x 与 size_y（size_i 表示序列中颜色为 i 的布丁的数量）。如果 size_x < size_y，我们暴力的合并，反之，则 swap(x,y)，并且做一个改名操作，将颜色 y 的名字改为颜色 x，将颜色 x 的名字改为颜色 y，然后再暴力合并。这块的实现可能会有一点小细节，要注意一下。

P4755 Beautiful Pair

题目大意：求对于所有的 (i,j)(i \le j)， a_i \times a_j\le \max(a_l,a_{l+1}...,a_{r})，的数量。

题解：首先，按照惯例，这种统计所有区间的问题有很多都是用分治做。

容易想到，我们可以按照最大值分左右区间，但是如果按照平常的分治思路，遍历整个分治区间，我们的时间复杂度很容易退化成 O(n^2)。

那我们能不能只遍历左右区间中长度较小的呢？答案是肯定的。如果我们遍历长度较小的区间，同时设 a_{mid} 为分值区间最大值，遍历到了 i，我们只需要在长度较大的区间查小于 \frac{a_{mid}}{a_i} 的数的数。

这找过程可以用树状数组实现，这个树状数组是一个类似桶的功能，但是 a_i 的值域很大，所以说我们可以考虑将每次查询都存下来，将 [l,r] 区间的答案容斥成 [1,r] 区间的答案 - [1,l-1] 区间的答案，再将原序列离散化。注：取最大值时用 ST 表。

对于时间复杂度的分析，我们可以按照启发式合并的思想，将分裂区间的操作逆过来，把一个个小区间合并，那我们每次便利的是小区间，然后遍历到每个数进行一次查询。时间复杂度 O(n \log^2 n)。

P15479 [CERC2012] Non-boring sequences

题目大意：判断一个整数序列的每一个连续子序列是否都包含至少一个独一无二的元素。

题解：考虑分治，先在一个区间内找到一个独一无二的元素，那么包含这个元素的所有在这个区间内的连续子序列一定是满足条件的。

所以说，我们可以以这个元素，把这个大区间分成左右两部分；如果一个区间内找不到一个独一无二的元素，那么这个区间内一定存在一个子序列，不包含至少一个独一无二的元素。

那么我们怎么找到一个独一无二的元素呢，很容易想到，维护一个 pre_i 表示 a_i 上一次出现的位置，再维护一个 nxt_i 表示 a_i 下一次出现的位置，那么对于区间 [l,r]，如果有一个下标 i(l \le i \le r)，使得 pre_i < l 且 nxt_i > r，那么对于这个区间，a_i 就是一个独一无二的元素。

但是我们找这个元素肯定是需要遍历整个区间的，如果出题人有意构造数据，那么时间复杂度会被卡到 O(n^2)。按照上一个题目的思路，我们如果只遍历分出来的较小的区间，那么时间复杂度是可以做到 O(n \log n) 的，那我们不妨同时遍历左右两边，找到第一个独一无二的元素这样时间复杂度就是正确的了。

树上启发式合并（DSU on tree）

树上启发式合并的一般做法是先找每个点的重儿子（子树大小最大的儿子），然后向下递归。每到一个节点，若这个节点有重儿子，则先递归其重儿子，然后将重儿子的信息 swap 上来（在 C++11 及以上，swap 一般是 O(1) 的，例如：map，vector，set......），然后一个一个合并其他的儿子，时间复杂度分析与先前相同。

CF600E Lomsat gelral

题目大意：给定一棵以 1 为根的树，每个点都有颜色，求对于所有点，其子树（包含这个点本身）内出现次数最多的颜色编号之和（可能不是一种颜色）。

题解：这几乎是树上启发式合并的模版题，可以对于每一个点，开一个 map，下标是颜色编号，值是这个颜色节点的数量，统计答案时，可以先继承当前节点重儿子的答案，然后在合并其他子树和它本身的时候再更新答案。

P3806 【模板】点分治

题目大意：给定一棵有边权的树，查询树上是否存在一条边权和恰好为 k 的简单路径。

（一些点分治是可以用树上启发式合并做的，但并不是全部，同时，树上启发式合并并不是点分治，这是两个完全不同的概念。）

题解：考虑树上启发式合并，对于每一个点，开一个 map，为了方便计算，map 中下标是节点的根节点的距离，只要 map 中有这个关键字，就代表有这个距离。

假设当前点为 u 且 dep_i 表示结点 i 到根节点的距离，在遍历子树的 map 时，当遍历到一个距离 l 时，只需要在 u 的 map 中查询 k + 2 \times len_u -l 是否存在即可。

值得注意的是，需要在查询后再将子树的信息合并到当前节点，要不然可能会查询到同一棵树的两个节点，而它们已经在它们的子树的递归过程中被计算了。

P4149 [IOI 2011] Race

题目大意：给一棵树，每条边有权。求一条简单路径，权值和等于 k，且边的数量最小。

题解：只需要把 map 中存储的值改成最小的深度，这样边的数量就可以用深度进行计算，按照和上一题一样的处理方式即可。

CF1709E XOR Tree

题目大意：每个点有点权，每次操作可以修改点权，求最少操作次数，使得没有一条简单路径，所有路径上的点的点权的异或和不为 0。

题解：如果我们一定要修改一个点的点权，那么最好是修改成很大的点权，这样是最优的，因为这样一定保证不存在一条点权异或和为 0 的路径。

经过上述分析，发现把这个点的点权修改成什么是不重要的。那么我们从下到上贪心的考虑，当我们枚举到一个点 u 的时候，我们一定要保证其每个儿子节点的子树内没有点权异或和为 0 的路径，然后我们合并的时候查找有没有点权异或和为 0 的路径，如果有我们就要强制清空该点存储的内容（可以用 set，map等数据结构）。

注意事项 1：一定要先查询，再加入。

注意事项 2：清空完后不要立即退出，别忘了 dfs 完所有的儿子再退出。

HDU-6109 数据分割

题目大意：给定一些 x_i=x_j 或 x_i \ne x_j 的限制，你需要划分这些限制，使得对于每组数据，去掉最后一个限制可以成立的，但加上最后一个限制不能成立。

题解：可以图论建模，如果两个点属于同一联通块，则说明这两个点值相同。那么限制 x_i = x_j 就等同于把 x_i 和 x_j 连边；限制 x_i \ne x_j 就等同于 x_i 所在的联通块与 x_j 所在的联通块不能连边。

什么时候加上一个限制是不能成立的，就是一个形如 x_i \ne x_j 的限制中 x_i 与 x_j 属于同一个联通块。但并不是每组数据的最后一个限制必须是形如 x_i \ne x_j 的，有可能是先有两个数不相等，但后面又来了一个这两个数相等，例如：第一个限制是 x_1 \ne x_2，第二个限制是 x_1 = x_2，那么必须要在第二个限制划分。

为了表示两个联通块合并成了一个联通块，很自然地想到并查集，即如果两个数有相同的父亲，那么认为这两个数在同一联通块内。但同时根据上文所述，我们必须维护出每个联通块对其他联通块的限制，这个我们可以拿一个 vector 去维护，要注意每个形如 x_i \ne x_j 的限制必须存储在这个联通块的父亲中。对于每一个这种限制，需要在 x_i 的父亲和 x_j 的父亲中加入这种限制。

按照这个思路，如果有一个形如 x_i = x_j 的限制，我们只需要遍历 x_i 和 x_j 中限制较少的联通块中的所有限制，判断这些限制是否合法，并将这些限制合并到另一个联通块中，然后更新并查集。

如果有一个形如 x_i \ne x_j 的限制，我们只需要找到两个联通块的父亲，如果两父亲相同，则限制不能满足；如果不同，则按上文方式加入限制。

P5290 [十二省联考 2019] 春节十二响

题目大意：将 n 个点分成若干组，每组中点与点之间不存在 祖先-后代 关系，最小化每组中最大值的和。

题解：首先考虑一个问题，我们如果要将两个长度为 n 和 m 的数组（n > m）分成 n 组，每组中只有 1 个或 2 个元素，如果一组中有两个元素，需保证这两个元素分别来自不同的数组，最小化每组中最大值的和。

猜一个结论：先把两数组从大到小排序，然后从前往后，把下标相同的两个数分为一组。这是一个直观的感觉，我们可以使用邻项交换证明，具体地，你可以交换一个排好序的数组中的前两项，然后与不交换的方案对比，可以发现不交换的方案是更优的，在这里不展开。然后就可以发现这个结论是正确的。

事实上，对于一个节点，它的不同子树中的点一定不是 祖先-后代 关系。所以说，合并这个点的子树就是在不断进行上述操作，而这个点本身和所有点都是 祖先-后代 关系，所以说它必须独立的加入序列中。

特别地，在这道题中，我们认为重儿子是深度最大的子树，因为序列中的元素个数与深度有直接关系。对于这道题，可以开 n 个优先队列完成上述操作，而且实际上，仔细分析一下，会发现每个节点只会执行取出和加入操作 1 次，所以说总时间复杂度是 O(n \log n) 的。

总结

启发式合并的本质是将较小的集合或者一些信息块插入较大的中，以保证时间复杂度，否则时间复杂度会假。这类问题时间复杂度一般是 O(n \log n) 或者 O(n \log^2 n)。

在序列问题中，如果题目中明确给了将什么完全修改为什么，那不妨考虑如果把操作反过来会不会有影响，如果有影响，可不可以做什么操作修补这个影响，如果逆操作是成立的，那么就可以向启发式合并思考。

在树上问题，树上启发式合并可以处理一些路径计数或者判断是否存在这种路径的问题，它的一个重要特点是问题支持合并操作，在合并时，应该考虑用什么数据结构更方便，可以考虑 map，vector，set，priority_queue。同时在写代码时要注意不是每个节点都有重儿子的，比如说：叶子结点。

完结撒花

感谢大家的观看，这篇文章就当这里啦。