[CF1930F] Maximize the Difference

下文用一个二进制数中为 $1$ 的位来表示一个数。

维护集合 $S$，每次插入一个数后查询集合中两个元素 $x\slash y$ 的最大值。$\slash$ 表示集合差。

我们考虑在每次加入 $x$ 后考虑这个集合的答案是否被 $x\slash y$ 或 $y\slash x$ 更新，其中 $y$ 是集合中原有的数。

对从大到小每一位依此贪心，于是问题就变成了，加入数并动态维护 $S$ 中是否存在 $x$ 的子集和超集。

朴素的暴力是加入一个数，遍历其所有子集和超集分别标记。不过注意到，如果 $S$ 中存在 $x$ 的子集，那么对于 $x$ 的所有超集 $y$，$S$ 中均存在 $y$ 的子集。

所以如果 $S$ 中已经存在 $x$ 的超集则返回，否则对 $x$ 分别去掉每一位后的集合递归地标记。子集同理。这样做的总时间复杂度为 $O(n\log n)$。