2023-06-24

LibreOJ β Round #2

A. 模拟只会猜题意

按照题意模拟即可。

时间复杂度 $\mathcal O(n^2 + m)$。

记 $f_{i, j}$ 表示考虑前 $i$ 个数 $S$ 能否取得 $j$。

枚举第 $i$ 个数的值进行转移，时间复杂度 $\mathcal O(n^5)$。

使用 std::bitset 优化到 $\mathcal O(\frac{n^5}{w})$。

答案一定不会变大。

每次 $x \rightarrow y$ 相当于合并 $x$ 和 $y$ 的集合，合并时每个点只会与其前驱后继产生贡献，所以可以用启发式合并 std::set 实现。

时间复杂度 $\mathcal O(n \log^2 n + m)$。

注意特判 $x = y$ 的情况。

对于有序的部分使用字典树维护，对于无序的部分使用前缀和维护，注意前缀和需要拆位。

对于异或操作使用全局异或标记，注意在末尾添加数时要异或标记。

时间复杂度 $\mathcal O((n + m) \log n \log v)$，空间复杂度 $\mathcal O(n \log^2 v)$。

不会。

可持久化启发式合并。

数据结构合并复杂度是均摊的，撤回操作导致了复杂度不严格。