思路

• 关键性质 1（奇数次） 区间 $[l,r]$ 内所有元素“逐个按位置”做异或，等价于“出现奇数次的所有不同值”做异或，因为相同值的偶数次会互相抵消。 令前缀异或为 $S[i] = a_1 \oplus a_2 \oplus \cdots \oplus a_i$，则

  $O(l,r)$ = $a_l \oplus a_{l+1} \oplus \cdots \oplus a_r$ = $S[r] \oplus S[l-1].$

• 关键性质 2（偶数且至少两次）

题目内容

给定一个包含 $n$ 个正整数的数组 $a_1,a_2,…,a_n$ ，以及 $q$ 次区间查询。查询有两种类型：

• 类型一：对区间 $[l,r]$ 中出现奇数次的所有值(即出现次数对 $2$ 取模为 $1$ 且至少出现一次)，将这些值逐一提取并计算异或和；

• 类型二：对区间 $[l,r]$ 中出现偶数次的所有值(即出现次数对 $2$ 取模为 $0$ 且至少出现两次)，将这些值逐一提取并计算异或和。

若区间内无符合条件的值，则结果为 $0$ 。

输入描述

第一行输入两个整数 $n,q(1≦n,q≦10^5)$ ，分别表示数组长度和查询次数。

第二行输入 $n$ 个整数 $a_1,a_2,…..,a_n(1≦a≦10^9)$ ，表示数组。

接下来 $q$ 行，每行输入三个整数op,l,™(1 ≤ op ≤ 2; 1≤l≤r≤n)，表示查询类型及区间左右端点。查询类型与题目描述一致。

输出描述

对每个查询，新起一行输出一个整数，表示对应区间的异或和结果。

样例1

输入

10 5
1 2 2 3 1 5 8 9 1 7
1 1 2
1 5 9
2 1 2
2 5 9
2 2 9

输出

3
4
0
1
3

说明

对于第一个查询：区间 $[1,2]=${$1,2$}，两者都出现一次(奇数次)，异或和 $1$ $xor$ $2=3$ ；

对于第二个查询：区间 $[5,9]=${$1,5,8,9,1$}，出现奇数次的值为 {$5,8,9$}，异或和 $5$ $xor$ $8$ $xor$ $9=4$ ；

对于第三个查询：区间 $[1,2]=${$1,2$}，无值出现偶数次，结果为 0；

对于第四个查询：区间 $[5,9]=${$1,5,8,9,1$}，仅值 $1$ 出现两次，异或和 $1$ ；

对于第五个查询：区间 $[2,9]=${$2,2,3,1,5,8,9,1$}，出现偶数次的值为 {$2,1$} ，异或和 $2$ $xor$ $1=3$ 。