操作的本质
每次选一个 b 中的数,把所有的 a 都按位或上这个数。
多次操作相当于先从 b 中选一些数,求出它们的按位或结果 B,然后把所有 a 都变成 a 按位或 B。
关键数
初始异或和 x = 所有 a 的异或结果。
y = 所有 b 的按位或结果(即 b 中所有数的按位或)。
对异或和的影响
如果 n 是奇数:
某一位如果 B 为 1,那么所有 a 的这一位都变成 1,奇数个 1 异或还是 1。
最终异或和 = x 按位或 B。
如果 n 是偶数:
某一位如果 B 为 1,那么所有 a 的这一位都变成 1,偶数个 1 异或变成 0。
最终异或和 = x 并且把 B 中是 1 的位清零(即 x 按位与 B 的按位取反)。
求最小值和最大值
n 为奇数:结果随 B 的增大而增大
最小取 B = 0,答案为 x
最大取 B = y,答案为 x 按位或 y
n 为偶数:结果随 B 的增大而减小
最小取 B = y,答案为 x 按位与(y 的按位取反)
最大取 B = 0,答案为 x
实现
每组数据算出 x 和 y,根据 n 的奇偶直接输出以上结果,复杂度 O(n+m)。