思路

• 关键性质 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（偶数且至少两次） 令 $D(l,r)$ 为区间 $[l,r]$ 内“不同值各取一次”的异或；令 $O(l,r)$ 为上式“奇数次值”的异或，则

题目内容

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

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

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