算法小站
首页
wiki
新鲜事
文章搜索
网站导航
回忆录
首页
wiki
新鲜事
文章搜索
网站导航
回忆录
登录
注册
算法基础
搜索
数据结构
字符串
数学
图论
动态规划
计算几何
杂项
wiki 主题
算法基础
搜索
数据结构
线段树
线段树单点修改
线段树区间修改
可持久化线段树
树链剖分
平衡树
FHQ-Treap
字符串
数学
图论
图的连通性
有向图的强连通分量
无向图的割点割边和双连通分量
动态规划
计算几何
杂项
启发式合并
高精度
主题名称
是否为父主题
是否为其添加wiki文章
取 消
确 定
选择主题
修改主题名称
修改父主题
修改wiki文章
取 消
删 除
修 改
算法基础
搜索
数据结构
字符串
数学
图论
动态规划
计算几何
杂项
杂项
启发式合并
高精度
[[ item.c ]]
0
0
启发式合并,树上启发式合并
## 启发式合并 ### 问题描述 记$$|S|$$为集合$$S$$中元素的个数,对于两个集合$$|S_x|, |S_y|$$,尝试将**小集合并入大集合中** 令$$|S_x| \leqslant |S_y|$$,那么 ```bash for z in Sx: 把 z 放入 Sy 中 清空 Sx ``` 这样做的时间复杂度是$$O(n \log n)$$ 的 **证明** 考虑每个元素的贡献,假设$$|S_x| \leqslant |S_y|$$,那么考虑$$|S_x |\to |S_x \cup S_y|$$ 合并之后的集合 $$|S2_x| \geqslant 2|S_x|$$,最后集合的大小是$$O(n)$$ 由此 $$|Sk_x| = O(n) \geqslant 2^{k} |S_x|$$,从而 $$k = O(\log n)$$ 也就是说,只需要合并$$O(\log n)$$次,所以代价是 $$O(n \log n)$$ **[HNOI 梦幻布丁](https://ac.nowcoder.com/acm/problem/20076)** **问题描述** $$n$$ 个布丁,$$m$$ 次操作,$$a_1,\cdots, a_n$$ 表示每个布丁的颜色 `1 x y` 将颜色 `x` 的布丁变成颜色 `y` `2` 询问一共有多少段颜色 **算法分析** > 询问多少段颜色,是比较简单的 ```bash for i = 2 to n: 只要 a[i] != a[i-1],ans += 1 ``` > 现在看修改颜色的时候,如何维护答案 比如将 `a[i]` 的颜色改为 `c`,段数会怎么变化呢?可以 $$O(1)$$ 来维护 如果`a[i] == a[i-1]`,那么 `i` 这个位置**对答案的贡献**是`1` 否则,对答案的贡献是`0`(`a[i]`和`a[i+1]`也是同理) ```bash modify 函数: ans -= ( a[i] != a[i-1] ) + ( a[i] != a[i+1] ) a[i] = c ans += ( a[i] != a[i-1] ) + ( a[i] != a[i+1] ) ``` > 具体怎么去修改颜色呢? 注意到,我们只需要求布丁有几段,一个位置$$i$$对答案的贡献,只和 `a[i] =? a[i-1], a[i] =? a[i+1]`有关,和`a[i]`的值具体是多少没有关系 将颜色`x`的布丁全部变成颜色`y`, **等价于**把颜色`y`的布丁变成`x` 根据启发式合并,只需要把颜色`x`的布丁**所有位置**用 `pos[x]` 存起来 保证`pos[x].size() <= pos[y].size()`,把 `pos[x]`中的元素合并到`pos[y]`中去 **特别注意** 启发式合并中可能会有`swap(pos[x], pos[y])`的操作,来保证`pos[x]`集合大小一定小于`pos[y]` > 比如 `{1, 4, 5, 7}`的颜色是`x`,`{2, 3]`的颜色是`y`,但是交换集合之后 `{1, 4, 5, 7}` 的颜色变成了`y`了,在`a[...]`数组这些位置的颜色也要对应改成`y` 执行上述 modify 函数,改的时候同时维护答案 **另外**,为了处理边界,在`a[0], a[n+1]`加入两个哨兵,值为`0` 这样答案就是`ans - 1`,避免了复杂的边界讨论 ### 启发式合并解决路径最小值 **问题描述** 给定$$n$$个点的树,和$$q$$个询问,每次询问路径$$u, v$$上的最小值 **算法分析** 考虑**将询问离线**,根据边权,**从大到小**加入边,当前边假设是$$(u, v)$$ 维护**两个点集**,$$u$$所在的点集是$$SU$$,$$v$$所在的点集为$$SV$$ (假设$$(u, v)$$的权值为$$w$$) 如果加入$$(u, v)$$**恰好**使得$$SU, SV$$**连通**,而此时恰好又有询问$$(qu, qv)$$ $$qu \in SU, qv \in SV$$,那么$$w$$就是询问$$(qu, qv)$$的答案 **证明** 对于两个点$$(u, v)$$,考虑路径$$u \to v$$,路径上删除任意一条边,都会使得$$(SU, SV)$$不连通 反之,**路径上**边权最小的边,就是满足 加入这条边后,$$(SU, SV)$$能够**恰好连通**,这样的边取权值最小的那个,就是答案 **算法实现** * 用并查集维护两个点集 * 对两个点集,相应地维护询问集合,即将询问`(qu, qv)`挂载到对应的点`(u, v)`上 * 启发式合并`su, sv`,同时维护答案 具体来说,按边权**从大到小**加入边,对于边$$(u, v)$$找到集合$$SU, SV$$ 启发式合并,尝试将$$SU \to SV$$,需要保证$$|SU| \leqslant |SV|$$,合并的同时维护答案 暴力检查$$|SU|$$中的每一个点,以及这个点上**挂载**的所有询问 > 如果用并查集的话,$$|SU|$$集合中的所有询问,就是`u = findpa(u)` `que[u]`中挂载的所有询问 即检查`que[u]`中的**所有询问** * 如果某个在`que[u]`中的询问`id`,这个询问已经**被解决**了,什么都不做 > 实际上可以从`que[u]`中删除,但`set`的删除带一个`log`,所以可以标记询问已被解决 > 这样可以提高程序运行时间 * 如果该询问的另一个端点在$$|SV|$$中,更新`ans[询问id] = w(u, v)` * 如果不在$$|SV|$$ 中,就把这个询问加入到$$|SV|$$中 做完之后,把$$SU$$中的点全部并入$$SV$$中,这里需要注意的是 我们需要知道**点到底在哪个集合中**,要用`belong[u]`去记一下 ## 启发式分治 **问题描述** 给定长为$$n$$的序列$$a_1, \cdots, a_n$$,定义序列$$a$$是一个好序列,当且仅当 它的**每一个子区间**$$[l, r]$$满足,至少存在一个元素$$x$$,它**只出现一次** **算法分析** > 什么情况下,一个序列**一定不是**好序列? 对于一整段$$a[1\cdots n]$$,只需要找到一个$$x$$,满足$$x$$在$$[1, n]$$中只出现一次 那么这个序列就**可能**是好序列,否则就**一定不是**好序列 > 假设我们找到了满足条件的$$x$$了,然后呢? $$x$$ 在一整段中都只出现了一次,那么对于**所有包含**$$x$$的子区间中 $$x$$ 也只出现一次,所以只需要检查不包含$$x$$的区间就可以了 `[1, pos[x]-1], [pos[x]+1, n]`,这样就可以考虑分治 > 考虑分治策略 对于$$[l, r]$$,我们找到整段区间中仅出现一次的元素$$x$$和它的位置 这个很容易找,只需要预处理,得到上一次出现和下一次出现, 满足`pre(x) < l`并且`nxt(x) > r`即可 问题是分治的时间复杂度,分治可能会存在**划分不均匀问题** 如果$$x$$每一次都在靠两端的位置,那么每一次找$$x$$的代价可能是$$O(n)$$的 总的复杂度退化到$$O(n^2)$$ 如果$$x$$在中间,那么分治策略复杂度是$$O(n\log n)$$,只需要考虑两端位置 解决方法是,**启发式分治**,用两个指针,每次分别从前往后,和从后往前找 尝试找到这样的`x` ```bash for (int pl = l, pr = r; pl <= pr; pl++, pr--) { if (pre[pl] < l && nxt[pl] > r) // 继续分治 if (pre[pr] < l && nxt[pr] > r) // } ``` > 启发式分治复杂度 $$T(n) = T(x) + T(n-x) + O(\min (x, n-x))$$ 也就是每一次合并的代价,只和**较小的那个集合**有关,复杂度$$O(n \log n)$$ ## DSU on Tree **算法概述** 我们需要维护一类有关**子树信息**的问题,比如树上点都有一种颜色,问任意一个点 它的子树中有多少种不同的颜色 一种算法思想是,考虑**子树合并**,合并的同时维护信息,并且转移到父亲,以此类推 子树合并可以考虑**启发式合并** > 简单来说,先把一个点的子树集合合并,然后再把集合和这个点本身的集合合并 **算法实现** 对于每个点,找到**集合大小最大**的儿子(也就是点个数最多),称为**重儿子** 其他的儿子称为**轻儿子** 假设当前的点是$$u$$,先把$$u$$的**重儿子**集合找出来,记为$$|HS|$$ 将$$u$$并到$$|HS|$$中,再把轻儿子集合并到$$|HS|$$中 > 具体来说,$$S(u)$$ 表示$$u$$这个点的集合,可以直接从重儿子继承过来 轻儿子依次合并到$$S(u)$$中 其实我们不需要维护轻儿子的集合,只需要`for`轻儿子子树中的所有节点 **代码实现** 先`dfs`整棵树,求出`dfs`序,并且维护树的结构 * `id[tot] = u`,记录`dfs`序下标`tot`对应原树的节点`u` * `sz[u]` 维护`u`及其子树的大小 * `hs[u] = v`,记录`u`的重儿子是`v` 接着做`DSU on Tree` `dfs(int u, int fa, bool keep)` * `keep` 参数的意义 如果一个点是重儿子,那么它的信息要**继承到父亲**上 如果是轻儿子,算出信息回溯的时候,不需要轻儿子携带的信息 `keep` 表示计算完成,回溯的时候,需不需要保留节点的信息 * 先`dfs`轻儿子,计算出轻儿子集合,和它携带的信息,`dfs(轻儿子v, u, false)` 再`dfs`重儿子,计算出重儿子集合和携带信息,`dfs(hs[u], u, true)` * 将`u`的所有轻儿子及其子树节点,加入到重儿子集合中 可以考虑`dfs`序列,如果`v`是**轻儿子**,它的子树就是`dfs`序中`l[v], r[v]` ```bash for x in [ l[v], r[v] ]: add( id[x] ) ``` 然后将`u`本身也加入到重儿子集合中,`add(u)` * 最后,如果`keep == false`,那么清空`u`及其子树集合中所有信息 `for x in [ l[u], r[u] ]`,执行`del(id[x])` ### 代码实现及应用 ```bash int n; vector<vector<int> > G(n+1); vector<int> l(n+1, 0), r(n+1, 0), id(n+1, 0), sz(n+1, 0), hs(n+1, -1); int tot = 0; function<void(int, int)> dfs_init = [](int u, int fa) -> void { l[u] = ++tot, id[tot] = u; sz[u] = 1; hs[u] = -1; for (auto v : G[u]) { if (v == fa) continue; dfs_init(v, u); sz[u] += sz[v]; if (hs[u] == -1 || sz[v] > sz[ hs[u] ]) { hs[u] = v; } } r[u] = tot; }; auto add = [](int u) -> void { // }; auto del = [](int u) -> void { // }; function<void(int, int, int)> dfs = [](int u, int fa, bool keep) -> void { // dfs light son for (auto v : G[u]) { if (v != fa && v != hs[u]) { dfs(v, u, false); } } // dfs heavy son if (hs[u] != -1) { dfs(hs[u], u, true); } // combine light son -> heavy son for (auto v : G[u]) { if (v != fa && v != hs[u]) { for (int x = l[v]; x <= r[v]; x++) add(id[x]); } } // add u add(u); if (!keep) { // clear info in node u for (int x = l[u]; x <= r[u]; x++) del(id[x]); } }; void solve() { dfs_init(1, 0); dfs(1, 0, false); } ``` **[CF600E. Lomsat gelral](https://codeforces.com/problemset/problem/600/E)** **问题描述** 给定$$n$$个节点的有根树,$$1$$号节点为根 每个节点都有一个颜色,第$$i$$号节点颜色编号为$$c_i$$ 如果一种颜色在以$$x$$为根的子树中**出现次数最多**,那么称它在$$x$$为根的子树中占主导地位 显然,同一棵子树中,可能有多种颜色占主导地位 对每一个$$i \in [1, n]$$,输出以$$i$$为根的子树中,占主导地位的颜色的编号和 **算法分析** 只需要稍微更改一下`DSU on Tree`的主过程,对于每个点$$x$$,需要知道以下信息并维护 * `c[x]` 表示节点`x`的颜色 * `cnt[ col ]` 表示颜色`col` 出现了多少次 * `maxcnt` 表示当前**出现次数最多的**是什么颜色 * `sum` 维护 `x` 及其子树,出现次数最多的颜色,它们的**编号和** 这样可以写出如下代码 ```bash auto add = [&](int x) -> void { int col = c[x]; cnt[col]++; if (cnt[ col ] > maxcnt) maxcnt = cnt[ col ], sum = 0; if (cnt[ col ] == maxcnt) sum += col; }; // 在 add(u) 之后,令 ans[u] = sum ``` **另外需注意**,清空的时候,同样上述信息要维护好 ```bash auto del = [&](int x) -> void { int col = c[x]; cnt[col]--; }; // 同 DSU on Tree 的模版 if (!keep) { del(id[x]); maxcnt = 0, sum = 0; } ``` ### IOI2011 Race **[IOI2011 Race](https://www.luogu.com.cn/problem/P4149)** **问题描述** 给一棵树,每条边有边权,求一条简单路径,权值和等于$$K$$,且边的数量最小 **算法分析** > 先考虑找到一条路径,使得它的权值和为 $$K$$,这应该怎么做呢? 注意到 `dis(u, v) = dep(u) + dep(v) - 2*dep( lca(u, v) )`,可以考虑**枚举LCA** 假设当前枚举的`LCA`是`x`,那么我们要在`x`的子树中找到两个点`u, v`,使得 $$\text{wdep}(u) + \text{wdep}(v) - 2\cdot \text{wdep}(x) = K$$,两个子树问题,可以考虑`DSU on Tree` **其中**,$$\textbf{wdep}(x)$$ 表示$$x$$到**根节点**路径上的**权值和** 对于每个点$$x$$,维护重儿子集合$$|SU|$$,并且`for`它的轻儿子$$v$$,对于每个$$v$$,先做一次查询 尝试在$$|SU|$$中找到一个点$$u$$,使得它到根节点路径的权值和为 `K + 2*wdep(x) - wdep(v)`,如果能找得到这样的`u`,怎么更新答案呢? > 考虑更新答案,答案要求边数量最小 考虑用哈希表维护,`mp[ wdep ] = dep`,简单来说,建立映射 `到根节点的权值和 --> min( 到根节点的最小边数 )`,对于一个点`u` `mp[ wdep(u) ] = min( ..., dep(u) )`,其中`dep(u)`就表示`u`到根节点的边数 哈希表维护**最小边数** `mp[ wdep ] = 到根节点的权值和是wdep时,此时到根节点的最小边数` > 这样,去维护**重儿子**的哈希表,就可以更新答案了 对于`d = K + 2*wdep(x) - wdep(v)`,如果能在哈希表中找到这样的`d` 那么它到根节点的最小边数是`mp[d]`,此时令 `ans = min(ans, mp[d] + dep[v] - 2*dep[x] )`,这样就更新完成了 > 接着尝试将`v`加入到哈希表中 实际上只需要更新`mp[ wdep(v) ] = min( mp[wdep(v)], dep[v] )` **值的注意的是**,在每一次`add`的时候,需要做`查询,更新` 在接下来`del`的时候,清空操作,实际上只需要把`mp`哈希表清空即可
看完文章有啥想法
发布评论
心里没有一点AC数
赞一个,支持一下 ```bash dfs(int u, int fa) { dfs 找到重儿子 } ``` $$\textbf{dfs} = \max( dp(u), dp(v) ) + w(u, v)$$![emoji](https://face.t.sinajs.cn/t4/appstyle/expression/ext/normal/33/2018new_xixi_thumb.png)
2023-06-29 02:38:03
点赞(1)
回复(0)
回复
目录
[[ item.c ]]
1094 人参与,1 条评论
心里没有一点AC数