AT_abc223_h [ABC223H] Xor Query

题目描述

给定一个长度为 $N$ 的正整数序列 $A = (A_1, \dots, A_N)$。

请处理 $Q$ 个查询。对于第 $i$ 个查询（$1 \leq i \leq Q$），判断是否可以从 $A_{L_i}, A_{L_i+1}, \dots, A_{R_i}$ 中选择至少一个元素，使得它们的异或和等于 $X_i$。

异或和的定义如下：对于整数 $a, b$，它们的按位异或 $a \mathrm{xor} b$ 定义为：

• $a \mathrm{xor} b$ 的二进制表示中，第 $2^k$ 位（$k \geq 0$）的数，如果 $a, b$ 的二进制表示中该位只有一个为 $1$，则为 $1$，否则为 $0$。

例如，$3 \mathrm{xor} 5 = 6$（二进制表示为：$011 \mathrm{xor} 101 = 110$）。

输入格式

输入以以下格式从标准输入读入。

$N$ $Q$
$A_1$ $A_2$ $\ldots$ $A_N$
$L_1$ $R_1$ $X_1$
$\vdots$
$L_Q$ $R_Q$ $X_Q$

输出格式

输出共 $Q$ 行。对于第 $i$ 个查询（$1 \leq i \leq Q$），如果可以从 $A_{L_i}, A_{L_i+1}, \dots, A_{R_i}$ 中选择至少一个元素，使得它们的异或和等于 $X_i$，则输出 Yes，否则输出 No。

输入输出样例 #1

输入 #1

5 2
3 1 4 1 5
1 3 7
2 5 7

输出 #1

Yes
No

输入输出样例 #2

输入 #2

10 10
8 45 56 9 38 28 33 5 15 19
10 10 53
3 8 60
1 10 29
5 7 62
3 7 51
8 8 52
1 4 60
6 8 32
4 8 58
5 9 2

输出 #2

No
No
Yes
No
Yes
No
No
No
Yes
Yes

说明/提示

数据范围

• $1 \leq N \leq 4 \times 10^5$
• $1 \leq Q \leq 2 \times 10^5$
• $1 \leq A_i < 2^{60}$
• $1 \leq L_i \leq R_i \leq N$
• $1 \leq X_i < 2^{60}$
• 输入均为整数。

样例解释 1

对于第 $1$ 个查询，可以选择 $A_1, A_3$，使得异或和为 $7$。对于第 $2$ 个查询，无论如何选择元素，都无法使异或和为 $7$。

由 ChatGPT 4.1 翻译