CF888G Xor-MST
Codeforces 分析 这种奇奇怪怪的生成树题考虑 Boruvka 算法。其核心思想是对每个连通块找到最近的连通块，然后合并。 对于这道题，我们考虑把所有数插入到一棵 Trie 中，那么对于每个节点，其左子树和右子树中必定只由一条边相连。这是因为在执行 Boruvka 算法的过程中，必定是左右子树先分别连通，然后再通过一条边合并在一起。 那么我们只需要知道两个数组间两两异或的最小值，将一...
Codeforces 分析 这种奇奇怪怪的生成树题考虑 Boruvka 算法。其核心思想是对每个连通块找到最近的连通块，然后合并。 对于这道题，我们考虑把所有数插入到一棵 Trie 中，那么对于每个节点，其左子树和右子树中必定只由一条边相连。这是因为在执行 Boruvka 算法的过程中，必定是左右子树先分别连通，然后再通过一条边合并在一起。 那么我们只需要知道两个数组间两两异或的最小值，将一...
Luogu UOJ 分析 考虑对每棵子树计算其 SG 函数值，即为每种删除情况得到的若干棵子树的 SG 函数的异或和的 mex。 于是我们要想办法求出每种选择情况得到的 SG 函数异或和的集合。 如果选择根节点，得到的就是它的每棵子树，子局面的 SG 函数值即为每棵子树的 SG 函数值的异或和。 如果选择了某棵子树中的节点，那么相当于这棵子树的 SG 函数异或和的集合异或上了其它子树 SG ...
Luogu LOJ 分析 因为 IP 地址可以看做长度为 $32$ 的二进制串，所以可以考虑用 Trie 树维护。 考虑查询。可以发现一个 IP 地址的匹配最大明确度是单增的，因此求出链上修改时间的单调栈即可。 代码 // ==================================== // author: M_sea // website: https://m-sea-b...
Luogu LOJ 分析 考虑每个节点用一个数据结构维护子树中所有点的信息。 则我们需要支持插入、合并、全局加 $1$、求全局异或和四个操作。 可以用 01-Trie 来维护。前面两个操作是基本操作。 考虑全局加 $1$。如果是一个偶数，它的最低位会变为 $1$；否则它的最低位会变成 $0$，然后给次低位加上 $1$，仍然可以根据次低位讨论。放到 Trie 树上就是从低到高枚举每一位，交换当...
Luogu BZOJ 分析 异或满足可减性，所以可以维护前缀和，然后 $\mathrm{a[p]\ xor\ a[p+1]\ xor\ ...\ xor\ a[n]\ xor\ x=s[p-1]\ xor\ s[n]\ xor\ x}$ 然后就只要维护$s[]$。添加很好维护，重点是如何查询。 此时查询转变为：已知$val=\mathrm{s[n]\ xor\ x}$，求一个$p\in[l-...