思路:
先将$a_j+x_i$看作一个整体, 与$b_i$求最大异或和.
求最大异或和使用贪心的方法, 即从高位往低位枚举, 尽量使某一位异或值为1.
假设前$i-1$位处理完后结果为$ans$, 则第$i$位为0时$a+x$取值范围是$[ans,ans+2^{i}-1]$, 为1时取值范围是$[ans+2^i,ans+2^{i+1}-1]$.
于是对于$a$, 两个取值范围为$[ans-x,ans+2^{i}-x-1]$ 和 $[ans+2^i-x,ans+2^{i+1}-x-1]$
问题便转换为数组区间$[l,r]$内是否有指定值域的数, 使用主席树即可.
代码:
1 |
|