解题思路

异或与最大化

异或运算满足对每一位独立影响的性质，要在区间 [l, r] 中选择一个数 $a$ 使得 $x\oplus a$ 最大，可从最高位到最低位逐位“贪心”决策：

1. 对第 $i$ 位，观察 $x$ 在该位的值 $x_i$。若想让异或结果该位尽可能为 1，应令 $a_i = x_i \oplus 1$；否则令 $a_i = x_i$。
2. 但直接取“相反位”可能会导致 $a$ 跳出区间 [l, r]，需维护两个状态：
   • gt：已构造的高位前缀是否严格大于 $l$ 的前缀；
   • lt：已构造的高位前缀是否严格小于 $r$ 的前缀。
3. 若 gt 为假，则新位 $a_i$ 需满足 $a_i \geq l_i$；若 lt 为假，则需满足 $a_i \leq r_i$。二者都满足才可取“理想”$a_i=x_i\oplus1$，否则退而求其次取 $a_i = x_i$。