UOJ Logo

NOI.AC

1S 512MB

#711. 子段与子段

Statistics

A. 子段与子段

题目描述

对于一个序列$a_1,a_2,\dots,a_n$,子段是指它的一个连续部分,即$a_l,a_{l+1},\dots,a_r$

容易发现,一个长度为$n​$的序列有$\frac{n(n+1)}{2}​$个子段。例如序列$3,7,4​$有下列子段:

$(3),(3,7),(3,7,4),(7),(7,4),(4)$

Mia希望分别求出这些子段的异或和,再将它们异或起来。但是Cierra觉得这太简单了,所以她提出了$q$个询问,每次给出一个区间$[L,R]$,希望你将这个下标区间对应的子段截取出来,回答上面的询问。

具体来说,对询问$[L,R]$,你需要回答$a_L,a_{L+1},\dots,a_R$的所有子段异或和的异或和。

输入格式

第一行包含两个用空格隔开的整数$n,q$

第二行包含$n$个用空格隔开的整数$a_1,a_2,\dots,a_n$

之后$q$行,每行包含两个用空格隔开的整数$L,R$,依次代表$q$组询问

输出格式

对每个询问输出一行,包含一个整数,为该区间所有子段异或和的异或和

样例输入

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

样例输出

2
6
0

数据限制

对于30%的数据,$n,q \leq 500$

对于60%的数据,$n,q \leq 5000$

对于100%的数据,$1 \leq n,q \leq 200000,0 \leq a_i \leq 10^9$,每一组$L,R$均满足$1 \leq L \leq R \leq n$

时空限制

1000ms, 512MB