2021牛客暑期多校训练营4 E.Tree Xor(dfs)

Tree Xor

https://ac.nowcoder.com/acm/contest/11255/E

Description

给出一棵树，权值未知，但是给出每条边两个端点权值的异或值，求原来的权值。

Solution

假设权值 $a[1] = 0$ ，那么从它开始进行一遍 $dfs$ 赋值可以得到所有点当前的权值 $a[i]$ 。当然 $a[1]$ 不一定等于 $0$ ，假设 $a[1] = x$ ，那么真实的 $a[i]' = a[i] \oplus x$ 。
现在给出每个 $a[i]'$ 的范围满足 $l[i] \leq a[i]' \leq r[i]$ ，即 $l[i] \leq a[i] \oplus x \leq r[i]$ ，设 $k = a[i] \oplus x$ ，等式两边异或上 $k \oplus x$ 得到 $x = a[i] \oplus k$ ，于是 $x$ 满足 $x \in \{a[i] \oplus k \ \ |\ \ l[i] \leq k \leq r[i]\}$ 。

于是现在转化成考虑以下问题：

给出 $n$ 个限制条件，求出它们之间的交集。(转换成求被覆盖 $n$ 次的线段长度)
对于每个能够取到符合条件的数字。我们可以用线段差分表示，例如 $[1, 5]$ 区间如果满足某个限制条件，那么标记 $(1, 1)$ , $(6, -1)$ , 这样在遍历 $[1, 5]$ 区间的时候得到的权值都是 $1$ ，到了 $6$ 这个点就变成 $0$ 。那么 $n$ 个条件都满足，只需要找到哪些点权值为 $n$ ，直接找出所有符合条件的线段长度即可。
如何打标记?

直接做 $[l_i, r_i]$ 不方便，不妨拆成 $[1, l_i - 1], [1, r_i]$ ，对于第一个区间 $[1, l_i - 1]$ ，符合条件打上 $-1$ 标签， $[1, r_i]$ 打上 $1$ 标签，最终 $[l_i, r_i]$ 上标签都是 $1$ ，符合我们的期望。

关于如何找到可行的区间?

考虑单独一对 $(l[i], r[i])$ 的操作，当搜索 $[1, l_i - 1]$ 时，对 $a[i]，l[i] - 1$ 搜索二进制上的每一位，情况无非就是 $00,01,10,11$ 四种情况，我们规定第一个二进制位表示 $l[i] - 1$ ，第二个二进制位表示 $a[i]$ ，在保证从高位到低位的情况下，维护当前前缀 $now$ 。

当出现 $11$ 时，因为 $l[i] - 1$ 当前位为 $1$ ，所以对于可选方案可以取 $0 / 1$ ，当取 $0$ 时，类似于数位 $dp$ ，当前不受 $limit$ 限制，后面的数字已经可以随便取了，而当前位异或值为 $1$ , 我们可以考虑该位为 $1$ 的所有数字，于是将这一 $bits$ 的所有数字 $[now + (1 << bits), now + (1 << (1 + bits)) - 1]$ 加入，当取 $1$ 的时候，该位为 $0$ , $now$ 不变， $dfs$ 下一层。
当出现 $10$ 时，因为当前位为 $1$ ，可以取 $0/1$ ，同理，取 $0$ 的时候解除 $limit$ 限制，后面二进制位可以任取搭配，当前位异或值为 $0$ ，所以可以加入 $[now, now + (1 << bits) - 1]$ ，如果取 $1$ 的话，异或值为 $1$ ，于是 $now = now + (1 << bits)$ ， $dfs$ 下一层。
当出现 $01$ 时，因为当前位为 $0$ ，任何数字都无法取到，但是异或值为 $1$ ，此时 $now = now + (1 << bits)$ ， $dfs$ 下一层。
当出现 $00$ 时，因为当前位为 $0$ ，任何数字都无法取到，异或值为 $0$ ，此时 $now$ 不变， $dfs$ 下一层。