RainFestival树

发现这个有点冷门，写一篇blog推广一下。 感谢教我这个trick的巨佬 @Rainfestival。 ~~这个trick好像没有名字，就叫它RainFestival树不过分吧~~ ## 问题 十分小清新：给定一个集合 $S$ ，动态加数（ $a_i \leq 2^{20}-1$ ），求 $max_{a_i \in S}(b \& a_i)$ ## 做法：开桶维护。 考虑两个数相与最大，肯定是从前往后，看每一位是否能够是 $1$ 。 假设我们枚举到第 $j$ 位 如果 $b$ 的第 $j$ 位是 $1$ ，那么 $a_i$ 这一位肯定最好是 $1$，（没有也没办法） 否则 $a_i$ 的这一位没有限制。 但是注意，我们在选择 $a_i$ 的过程中，决策集合在逐渐减小，也就是这一步是 $1$ 不能干扰以前确定是 $1$ 的位，但是更高的位也不全是有限制的。 怎么办呢？ 维护一个临时变量 $S$ ，如果现在确定第 $k$ 位是 $1$ ，那么就令 $S \leftarrow S | (1 << k)$ 那么我们每次查询第 $j$ 位是否可能是 $1$ ，相当于查询是否 $\exist a_i,a_i | (S | (1 << j)) = a_i$ 。 那么这个问题就可以通过 ~~FMT~~ 解决，但是如果是动态加数，可以通过 ~~CDQ套FMT~~ 解决。 这里有一种常数小且好写的做法，把上述过程想象为 $a_i$ 覆盖它的子集（每个 $a_i$ 会对它的子集产生贡献）。 那么可以想到做法，每次插入一个 $a_i$ 如果它没有被覆盖，就覆盖它，同时枚举 $a_i$ 的每一位删除，递归覆盖。否则被覆盖了，就返回（它的子集一定被覆盖过），这样，每个数只会被覆盖到一次，总复杂度 $\Theta(Q + 2^{20})$ 。 ~~讲来讲去就一句话~~ ## 例题：最大生成树，每个点有权值，边权为点权按位与。 原题[UOJ176](https://uoj.ac/problem/176)。 考虑 Boruvka （此处略去），那么每轮我们要干的事情是查 $max( \forall a_i \in S,\forall b_i \notin S,a_i \& b_i)$ 这里有集合内外之分，但是我们可以魔改之（拜谢bot），把覆盖标记改成染色，每个集合对应一种颜色，如果一个点被当前未被当前集合染色，且颜色数不足两种，那就递归染色，易证每个数只会被染色两次，复杂度 $\Theta((n + 2^{20}) \log n) $ 。