题目描述
一家餐厅有 \(n\) 道菜，编号 \(1, 2, \ldots, n\)，大家对第 \(i\) 道菜的评价值为 \(a_i\)。有 \(m\) 位顾客，第 \(i\) 位顾客的期望值为 \(b_i\)，而他的偏好值为 \(x_i\)。因此，第 \(i\) 位顾客认为第 \(j\) 道菜的美味度为 \(b_i\oplus (a_j + x_i)\)，\(\oplus\) 表示异或运算。
第 \(i\) 位顾客希望从这些菜中挑出他认为最美味的菜，即美味值最大的菜，但由于价格等因素，他只能从第 \(l_i\) 道到第 \(r_i\) 道中选择。请你帮助他们找出最美味的菜。
对于 \(100\%\) 的数据，满足 \(1 \le n \le 2 \times 10^5\)，\(0 \le a_i,b_i,x_i < 10^5\)，\(1 \le l_i \le r_i \le n\)（\(1 \le i \le m\)），\(1 \le m \le 10^5\)。
解析
看到异或就考虑按位贪心一下。
从高位按二进制开始枚举，记录一个满足题目限制的 \(ans = a_j + x_i\).
设当前枚举到第 \(i\) 位，\(a, b\) 在这一位上的值分别为 \(a'_i, b'_i\).
分类讨论：
- 若 \(b'_i = 1\)，要使答案最大即是让 \((x + a)\) 的这一位为 \(0\)，容易发现当且仅当 \(a \in [x' -, ]\)