区间异或查询（前缀异或）

题目名称

区间异或查询

---

一、题目描述

小明正在研究一种特殊的数字运算。

与普通加法不同，计算机中还有一种按位运算：

异或运算（XOR）。

两个整数进行异或时，对它们二进制的每一位分别比较：

• 相同为 0
• 不同为 1

记作：

$\oplus$

例如：

5 ⊕ 3

二进制：

5 = 101
3 = 011

异或：

101
011
---
110

结果：

6

---

现在给定一个长度为 n 的整数数组：

$a_1,a_2,...,a_n$

需要回答 q 次询问。

每次询问给出两个整数：

$l,r$

请计算：

$a_l\oplus a_{l+1}\oplus...\oplus a_r$

并输出结果。

---

二、异或运算说明

异或运算满足以下性质：

1. 自身异或等于0

$x\oplus x=0$

例如：

7 ⊕ 7 = 0

---

2. 与0异或不改变

$x\oplus0=x$

例如：

8 ⊕ 0 = 8

---

3. 满足交换律

$a\oplus b=b\oplus a$

因此：

多个数字异或时，顺序不会影响结果。

---

三、任务要求

对于每一次询问：

计算：

$_l\oplus a_{l+1}\oplus...\oplus a_r$

并输出答案。

---

四、输入格式

输入包含：

第一行

两个整数：

n q

其中：

• n 表示数组长度
• q 表示询问次数

---

第二行

输入 n 个整数：

a1 a2 ... an

表示数组元素。

---

接下来 q 行

每行两个整数：

l r

表示一次查询：

查询区间：

[ [l,r] ]

---

五、输出格式

对于每一次查询：

输出一个整数：

$a_l\oplus a_{l+1}\oplus...\oplus a_r$

每个答案占一行。

---

六、数据范围

保证：

$1\le n,q\le100000$

$0\le a_i\le10^9$

$1\le l\le r\le n$

---

七、样例1

输入

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

---

输出

0
0
3

---

八、样例解释

数组：

a:

1 2 3 4 5

---

第一次查询

查询：

1 3

计算：

$1\oplus2\oplus3$

过程：

1 ^ 2 = 3

3 ^ 3 = 0

答案：

0

---

第二次查询

查询：

2 5

计算：

$2\oplus3\oplus4\oplus5$

过程：

2^3=1

1^4=5

5^5=0

答案：

0

---

第三次查询

查询：

3 3

只有：

a3=3

答案：

3

---

九、样例2

输入

6 4
7 8 3 5 6 1
1 6
2 4
3 5
5 5

---

输出

6
14
0
6

测试点编号	难度层级	n	q	数据特征	覆盖点
1	弱数据	1	1	单元素 0	最小规模、l = 1
2			3	单元素重复查询	多次查询稳定性
3		5	4	小规模连续数	整段、前缀、中段、单点
4		6	5	全相同元素	重复值抵消、奇偶长度
5	正常数据	8	6	0 与成对重复值	0、跨段抵消
6		10		2 的幂位模式	按位异或特征
7		12	7	中等规模混合查询	首尾、内部、长区间
8		15	8	重复值与 0 交错	多块抵消
9	极限数据	20	10	查询较多，数值混合	输出行数与顺序
10		30	12	伪随机分布	综合长短区间
11		25	10	接近 int 正数上界	大数位运算
12		50	15	最大综合组	首尾边界、中心单点、压力混合