[R15D]二维异或和 - 代码源竞赛平台

时空限制

1S/512M

题目描述

给定一个长度为 $n$ 的整数数组 $A$。

定义区间 $[L,R]$ 的二维异或和为 $\sum_{i=L}^R\sum_{j=L}^R A_i\oplus A_j$，这里的 $\oplus$ 表示按位异或运算。

有 $q$ 个询问，第 $i$ 个询问求区间 $[L_i,R_i]$ 的二维异或和。

格式

输入格式

第一行包含两个整数 $n,q$，分别表示数组 $A$ 的长度和询问的数量。

第二行包含 $n$ 个整数 $A_i$。

接下来 $q$ 行每行两个整数 $L_i,R_i$，表示第 $i$ 个询问。

输出格式

输出 $q$ 个整数，第 $i$ 个整数表示第 $i$ 个询问的答案。

样例

样例输入 #1

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

样例输出 #1

12 10 0

样例解释 #1

第 $1$ 个询问的答案为 $(1\oplus 1)+(1\oplus 3)+(1\oplus 2)+(3\oplus 1)+(3\oplus 3)+(3\oplus 2)+(2\oplus 1)+(2\oplus 3)+(2\oplus 2)=0+2+3+2+0+1+3+1+0=12$。

第 $2$ 个询问的答案为 $(2\oplus 2)+(2\oplus 7)+(7\oplus 2)+(7\oplus 7)=0+5+5+0=10$。

第 $3$ 个询问的答案为 $6\oplus 6=0$。

数据规模

对于 $20\%$ 的数据，$n\leq 300$，$q\leq 500$。

对于 $60\%$ 的数据，$n\leq 10000$，$q\leq 500$。

对于 $100\%$ 的数据，$1\leq n\leq 3\times 10^5$，$1\leq q\leq 3\times 10^5$，$1\leq A_i\leq 10^6$，$1\leq L_i\leq R_i\leq n$。