CSP 考前快速复习（S 组）上

作者：云斗官方教研团队 yummy 老师

语法特性

类

事实上 class 和 struct 可以完成的东西基本相同，语法也很接近，加上这是复赛，你自己可以决定用什么语法，你并不需要特别关注这一块内容。

但是成员函数和运算符重载，如果用得好可以让 coding 非常舒服。

对于运算符我一般喜欢写在外面，例如 bool operator < (edge x,edge y){return x.dis<y.dis;} 之类，毕竟这样可以让 $x,y$ 地位更加对称。

如果出现多个功能类似的数据结构（如多棵线段树），我们可以用类或结构体把数据结构装起来。

pair 和 tuple

相当于自己写 struct，我个人不是很建议大量使用，因为一旦使用你就需要自己记住 first 是什么，second 是什么，如果将变量意义在 struct 的分量名称中体现出来，可以减小出错概率；另一方面 tuple 的语法更加复杂。

(unordered_) (multi) set/map

在 STL 容器中出现频率相当高，在我的代码习惯中仅次于 vector。很多人觉得 STL 可能会常数太大，但是在当下的评测环境，加上这是 CSP，我们还不需要考虑这些。

unordered 系列基于哈希表，期望 $O(1)$，最坏 $O(n)$，适用于搜索对象等没什么规律的东西；没有 unordered 的系列基于红黑树，是稳定 $\log(n)$ 的，适用于输入数据等出题人可以刻意构造的场合。

但是注意，multiset 中，count 函数时间复杂度为 $O(\log n+c)$，其中 $c$ 为出现次数，所以在元素大量重复时可能超时，正确的做法是使用 map 代替 multiset。

另一个需要注意的地方是 lower_bound,upper_bound 的正确写法。更多关于 STL 的信息可以参考 cppreference。

其他函数和容器

deque 从功能上讲是比 vector 更强大的工具，前后都可以 $O(1)$ 地插入或删除。

STL 的所有容器（除了 array），使用 swap 函数交换的时间复杂度都是 $O(1)$。

next_permutation 可以用于求下一全排列，可用于枚举全排列。

冷知识：vector, set 等支持比较运算符，规则是比较字典序。

序列上数据结构

单调栈，单调队列，笛卡尔树

非常巧妙的数据结构，除了优化枚举、优化 DP 外，以其为代表的时间复杂度分析方法也值得关注。

务必注意边界特判问题，尤其注意检查单调栈是否非空。我一般先在单调栈里面塞入一个无穷大或负无穷大，以保证非空。如果时间限制真的很充裕你甚至可以在单调队列里先塞 $n$ 个无穷大。

笛卡尔树在我学会后，认为它非常适合用来分析区间最值问题，不管是直接在笛卡尔树上做题还是仅仅用笛卡尔树证明结论。推荐复习一下洛谷模板题。

并查集

判定连通性的利器，码量非常小，变形非常多。

虽然理论上路径压缩但不启发式合并的时间复杂度是 $O(\log n)$ 而非 $O(\alpha(n))$ 的，但是目前没见过哪个出题人卡这个。然而，对于一些可撤回并查集（撤回最后的若干操作）无法路径压缩，就必须启发式。

并查集一个很综合的应用可以参考云斗 10 月 Golden Round 第 4 题。

二叉堆和优先队列

考纲中认为优先队列是线性结构，然而 priority_queue 的实现是二叉堆。

个人认为考场上手写二叉堆是不必要的，priority_queue 可以解决二叉堆几乎所有需求。pb_ds 也不是必需品。

ST 表

用于维护静态信息。经典应用是维护区间最值以及衍生出来的静态树上求 LCA。

事实上，只要一堆数字中某一个数字多重复几次对答案没有影响，都可以使用 ST 表。

$\gcd$，按位与、按位或都可以 ST 表维护都是经典题，格局打开，区间 LCA，甚至线性基都可以。

树状数组

用于维护单点更新，前缀查询。所以如果单点更新，区间某种运算，但是这个运算不可逆（如 $\max$）就不可以使用树状数组。

很多问题上树状数组的思路会比线段树更不直接，而且感觉好久没看见树状数组的题了。

树状数组上可以二分，查找前缀和 $\ge x$ 时前缀长度至少是几，参考冰火战士。

线段树

变形最多的数据结构，在提高组的所有数据结构中，对要维护的运算要求是最低的（只要有结合律、单位元即可，不要求可逆）。你甚至可以发现，除了并查集以外所有的数据结构都可以用线段树替换（时间复杂度可能会比原来的数据结构多个 $\log$）。

线段树上同样可以二分，且思路比树状数组更直接。

字典树

字典树可以维护多个字符串，并查询字符串前缀。

常见的另一种字典树是 01-trie，用于维护数字的二进制表示。只要把维护的数字当成下标，给 01-trie 的每个结点记录区间值、lazy tag，就可以承担线段树功能，且无需离散化。

NOIP2021，NOI2022 均涉及了线段树合并（其中的线段树是 01-trie 变形而成），然而 NOI2022 根据考试情况看，map 启发式合并似乎跑得更快，这也启示我们可以用相关技巧在时间不够时用一些技巧减小码量。

哈希、哈希表

不保证今年不会“不可以总司令”（笑）。因为这里不是 CF，所以你写哈希被卡的概率大幅下降，但是仍然推荐背几个大质数。

哈希因为通常有大量取余，所以常数还是要留意一下的。之前一次 NOI Online的时候，我写了哈希，然后自己担心被卡于是写了双哈希，本来能 AC 的题目喜提 TLE，和暴力一个分。

哈希表我一般使用 unordered 系列，相比于自己写，正确性保障高很多。