CF1968F.Equal XOR Segments

普及+/提高

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

我们称一个数组 $x_1,\dots,x_m$ 是有趣的，如果可以将该数组分成 $k>1$ 个部分，使得每一部分的按位异或（bitwise XOR）结果都相等。

更正式地说，你需要将数组 $x$ 分成 $k$ 个连续的区间，每个元素必须且只属于一个区间。设 $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 个询问，这些子数组都不是有趣的。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页