← 返回题目列表

Codeforces · 1968/F

F. 相等的 XOR 段

中文机器翻译题面 查看原题

如果可以将数组分为 $$$k>1$$$ 部分,以便每个部分的值按位异或相等,那么我们称数组 $$$x_1,\dots,x_m$$$ 有趣。

更正式地说,您必须将数组 $$$x$$$ 拆分为 $$$k$$$ 连续段,$$$x$$$ 的每个元素必须恰好属于 $$$1$$$ 段。令 $$$y_1,\dots,y_k$$$ 分别为每个部分的元素的异或。那么 $$$y_1=y_2=\dots=y_k$$$ 必须满足。

例如,如果 $$$x = [1, 1, 2, 3, 0]$$$,则可以按如下方式拆分:$$$[\color{blue}1], [\color{green}1], [\color{red}2, \color{red}3, \color{red}0]$$$。确实$$$\color{blue}1=\color{green}1=\color{red}2 \oplus \color{red}3\oplus \color{red}0$$$。

给你一个数组 $$$a_1,\dots,a_n$$$。您的任务是回答 $$$q$$$ 查询:

- 对于固定的$$$l$$$, $$$r$$$,判断子数组$$$a_l,a_{l+1},\dots,a_r$$$是否有趣。

输入

第一行包含一个整数 $$$t$$$ ($$$1\le t\le 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$1 \le q \le 2 \cdot 10^5$$$)——分别是数组中的元素数量和查询数量。

下一行包含 $$$n$$$ 整数 $$$a_1,\dots,a_n$$$ ($$$0 \le a_i < 2^{30}$$$) — 数组的元素。

接下来的 $$$q$$$ 行包含两个描述查询的整数 $$$l$$$ 和 $$$r$$$ ($$$1 \le l < r \le n$$$)。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

保证所有测试用例的 $$$q$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个查询,如果子数组有趣,则输出“YES”,否则输出“NO”。

在任何情况下都可以输出“Yes”和“No”(例如,字符串“yES”、“yes”和“Yes”将被识别为正确答案)。

示例

输入 #1

4
5 5
1 1 2 3 0
1 5
2 4
3 5
1 3
3 4
5 5
1 2 3 4 5
1 5
2 4
3 5
1 3
2 3
7 4
12 9 10 9 10 11 9
1 5
1 7
2 6
2 7
11 4
0 0 1 0 0 1 0 1 1 0 1
1 2
2 5
6 9
7 11

输出 #1

YES
YES
NO
NO
NO

YES
NO
NO
YES
NO

NO
NO
NO
NO

YES
NO
YES
YES

注意

第一个测试用例的说明:

第一个查询在语句中进行了描述。

在第二个查询中,我们应该除$$$[1,2,3]$$$。可能的除法是$$$[1,2],[3]$$$,因为$$$1\oplus 2=3$$$。

可以看出,对于查询 $$$3,4,5$$$,子数组并不重要。