郊游

首先需要快速找到当前适配度最大的一对小朋友。容易发现 \(a,b\) 的适配度即为 \(a,b\) 二进制下最长公共后缀的长度，于是先翻转所有数的二进制串并插入到 Trie 中。那么 \(a,b\) 的适配度即为 \(a,b\) 所代表叶子节点的 \(\rm LCA\) （最近公共祖先）深度。

若 Trie 中以 \(x\) 为根的子树中仍有大于 \(1\) 个点未匹配，那么不会选择一对 \(a,b\) 满足 \(a\) 在 \(x\) 子树内而 \(b\) 不在。即每个子树内最多留下一个数未被匹配。

于是设 \(dp_x\) 表示 \(x\) 子树内已匹配的匹配值异或和，\(a_x\) 表示 \(x\) 子树内未匹配的数（若不存在未匹配的数，\(a_x=-1\) ）。转移时只有当 \(a_{ls}\not=-1\) 且 \(a_{rs}\not=-1\) 时那么可以将两个数匹配，其余情况均保留未匹配数。

task 1

暴力的删除每个数，然后做上述 \(dp\) 即可。时间复杂度 \(\mathcal O(n^2\log W)\)。其中 \(W=\max w_i\) 。

task 2

发现最终的 Trie 是一颗完全二叉树，所有的叶子将会直接与兄弟匹配，贡献 \(0\) 的匹配度。而删除 \(x\) 后会使得原本和 \(x\) 一组的数字单独被分为一组。时间复杂度 \(\mathcal O(n)\)。

task 3

给定条件就是从一棵完全二叉树中删去几个数。考虑类似 task2 的条件，每删除一个数 \(x\) 就会导致原本与 \(x\) 形成匹配的数变成未匹配数。那么最多删除 \(700\) 个数，即最多有 \(700\) 个未匹配数，按照 task 1 的方法做即可。

task 4

若我们删除的数字为 \(w\) ，那么只有满足子树内包含 \(w\) 的节点的 \(dp\) 和 \(a\) 会发生变动。我们只需要最开始预处理所有点的 \(dp\) 值，然后每次询问暴力更新这 \(\mathcal O(\log W)\) 个节点的值即可。时间复杂度 \(\mathcal O(n\log W)\)。