题解：P13997 【MX-X19-T6】「FeOI Round 4.5」はぐ

T6 最简单的一集。

考虑拆位，对于每一位只需要计算出有多少个数在这一位上为 $1$ 即可。根据经典套路，维护这些数的后 $i$ 位，如果 $a_i+b_i(a_i,b_i\lt 2^{i+1})\in[2^{i},2^{i+1}-1]\cup [2^{i}+2^{i+1},2^{i+2}-1]$ 那么 $a_i+b_i$ 的第 $i$ 位为 $1$。所以我们拆位后只需要维护 $a_i+dep_i$ 或 $a_i-dep_i$ 值域一段区间里的数的个数奇偶性即可。

直接树剖太蠢了，注意到这里只需要求奇偶性，容易想到出栈序 trick，我们在入栈和出栈时都将节点压入序列，查询时只需要查询路径两个端点入栈时刻之间的位置即可。由于不在路径上的节点必然出现偶数次，在路径上的节点必然存在奇数次，所以不在路径上的节点对答案没有影响。

最后还有一点小细节，$a_u-dep_u$ 为负数怎么办。容易想到不用去管它，当作对 $2^{i+1}$ 取模做即可。

代码非常好写，没有任何细节。