#489. 统计区间奇偶数

统计区间奇偶数

问题描述

给定一个含有 nn 个正整数的数组 aa 并给出 qq 次询问。

询问有两种:

第1种: 1 l r :表示求 alal+1...ar1ara_l, a_{l+1},... ,a_{r-1} ,a_r 中, 出现奇数次的数的异或和。

第2种: 2 l r : 表示求 alal+1...ar1ara_l, a_{l+1},... ,a_{r-1} ,a_r 中, 出现偶数次的数的异或和。

注意,这两种询问都是将区间内符合条件的每个数字,单独提一个出来,然后对这些数字做异或和,例如对于第二种询问,询问的区间里的数为 [1122][1, 1, 2, 2] ,此时 1122 都出现偶数次,都符合第二种询问的条件,答案为 12=31 \bigoplus 2 = 3

特别地,当数组 aa 在区间 [lr][l, r] 内的数的出现次数都不符合询问条件时,输出 00

输入格式

输入的第一行包含两个正整数 nnqq ,分别表示数组元素的个数和查询的次数。

输入的第二行包含 nn 个正整数,第 ii 个数字为 aia_i

接下来的 qq 行, 每一行描述一个查询,由三个整数 oplrop, l, r 组成,分别表示询问种类和查询段的左、右边界。

输出格式

对于每个询问按顺序输出对应答案.

输入样例

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

评测数据规模

对于所有评测数据: 1n1051 \le n \le 10^51q1051 \le q \le 10^5op[12]op∈[1, 2]1lrn1 ≤ l ≤ r ≤ n