RainFestival树

cool_milo · 2023-07-19 11:20:44 · 个人记录

发现这个有点冷门，写一篇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。

考虑 Boruvka （此处略去），那么每轮我们要干的事情是查 max( \forall a_i \in S,\forall b_i \notin S,a_i \& b_i)
这里有集合内外之分，但是我们可以魔改之（拜谢bot），把覆盖标记改成染色，每个集合对应一种颜色，如果一个点被当前未被当前集合染色，且颜色数不足两种，那就递归染色，易证每个数只会被染色两次，复杂度 \Theta((n + 2^{20}) \log n) 。