UOJ Logo

NOI.AC

3S 256MB

#125. C

统计

【题目描述】

初始给定n 个卡片拍成一排,其中第$i$个卡片上的数为$x[i]$。

有q 个询问,每次询问给定$L$ 和$R$ 表示,询问的区间$【L,R】$内的卡片所有出现了偶数次的数的异或和是多少。

【输入格式】

输入文件 C.in

输入一行两个整数 $n,q$。

第二行 n 个整数,第 i 个数为 $x[i]$。

接下来 q 行,每行两个整数 $L$ 和 $R$,表示询问的区间。

【输出格式】

输出文件 C.out

输出 q 行,其中第 i 行表示第 i 次询问的区间出现偶数次的数的异或和。

【样例输入 1】

3 1 
3 7 8 
1 3

【样例输出 1】

0 

【样例输入 2】

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

【样例输出 2】

0 
3 
1 
3 
2

【数据范围】

对于$20%$的数据,$n,q \le 1000$;

对于另外$20%$的数据,$n,q \le 50000,a[i] \le 10$。

对于 100%的数据,$n,q \le 1000000,0 \le a[i] \le 10^9$。