『dsu、Trie』Day7

Stamp Rally

kruskal 重构树板子，套上二分求一下祖先即可。

AND-MEX Walk

注意到答案只可能是 0,1,2。

因为 1 和 2 显然不能同时存在。

证明：可知边权序列不增，如果前面出现 2 则说明第 1 位是 0，由于是与运算所以不可能有 1 了。

判断 0 和 1 即可。

0 好判断，只要全不为 0，也就是最后一个数不为 0。那么必然有一位满足所有 \(w_i\) 在第 \(i\) 位都是 \(1\)。用 log 个并查集即可。

1 有点难。首先肯定保证会有一段 0 的后缀，不然答案是 0。那么前面的数都要 > 1。

所以只要有 1 位使得这些数都是 1，基本就符合条件了。

考虑这种情况，前面一堆 \(w=3\)，中间有一个 \(w=1\)，答案就不是 1 了。

所以还要保证，我们使用 1 ~ w 的位数去一直走，走到最后一个数后面是一个偶数，消除这种可能，这是容易的。

销售基因链

将字符串排序，可以在 trie 上找到给出的前缀对应的区间。

然后用可持久化 trie 找区间内这样的后缀有几个。

注意 trie 循环外面要更新 son。