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

piggy123 · 2025-09-08 21:55:35 · 题解

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} 取模做即可。

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