数据结构专题练习

Lgx_ / 2024-11-17 / 原文

[CF1168D] Anagram Paths

link

设 $f_{u, i}$ 表示 $u$ 子树中字符 $i$ 至少需要出现的次数，那么 $f_{u, i} = \max\limits_{v \in son(u)} f_{v, i}$。整棵树合法当且仅当所有叶子深度相同，且对于所有点 $u$ 满足 $\sum\limits_i f_{u, i}\le d_u$，其中 $d_u$ 为 $u$ 子树深度。发现二叉树的条件比较特殊，如果把所有二度点缩点，发现每个叶子的深度都是 $\mathcal O(\sqrt n)$ 的。直接暴力跳父亲即可。

启示：时间复杂度分析。

[SNOI2020] 字符串

link

暴力做，可以把两个字符串的所有长度为 $k$ 的子串全部扔进 trie 里面，然后贪心匹配。

可以看出需要建立 SAM。由于是固定相同前缀，存在不同后缀，所以考虑建立两个串反串的广义 SAM，然后和 trie 就没什么区别了。

启示：观察数据结构的特点，进一步扩展。

[Ynoi2001] 冷たい部屋、一人

link

考虑每种数按出现次数根号分治。

对于出现次数 $\le B$ 的数，发现总对数 $\le \mathcal O(nB)$。考虑暴力枚举，用 ST 表求出每一对相同的数之间的 min 和 max，将 max 扫描线。注意到空间是带根号的，考虑对于每一个 max 值求出其管辖的范围，记录并扫描线。

对于出现次数 $> B$ 的数，种数 $\le B$，考虑对每一种数都做一遍莫队。具体的，将询问离散化（需要线性），然后把每两个相邻相同数字之间的 $[\min, \max]$ 挂到对应 $\min$ 和 $\max$ 位置上，不难发现每个位置至多挂两个区间。然后做回滚莫队，链表维护。

启示：根号分治大法好。

[Ynoi2011] WBLT

link

这种题一定是需要 bitset 的，考虑用莫队处理出每个询问区间出现的数的 bitset。然后将该 bitset 分裂为若干个长度为 $b$ 的小 bitset，依次按位与起来。

当 $b$ 过小时复杂度会出错，考虑类根号分治，当 $b\le 64$ 时，每种数做一次 bitset。

启示：bitset 与莫队结合；类根号分治。

[Ynoi2002] Optimal Ordered Problem Solver

link

[CF1876G] Clubstep

link

考虑一个询问，依次 $i = r\dots l$，若 $x > a_i$，则造成 $\lceil \frac {x - a_i} 2\rceil$ 贡献，然后 $x\gets \lfloor \frac {x + a_i} 2 \rfloor$。

考虑离线扫描线，每次加入若干个 $x$，或者删掉若干 $x$，我们需要维护一个 $x$ 的集合，每经过一个 $a_i$ 都要更新一遍。这个很难维护，接下来是魔法。设当前集合中 $x$ 从小到大为 $x_{1\dots k}$，考虑势能 $f = \sum\limits_{i = 2} ^ k \log_2 (x_i - x_{i - 1})$，发现每更新一个 $x$，$f$ 至少减小 $1$。$f$ 增加值总和为 $\mathcal O(q\log V)$，所以可以暴力更新那些 $> a_i$ 的 $x$。对于相同的 $x$ 势能分析失效，需要用并查集将其合并，并查集需要带权。时间复杂度 $\mathcal O(n + q\log ^2 V)$。